Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

K. Buchin; I. Kostitsyna; M. Löffler; R.I. Silveira

doi:10.1137/1.9781611973754.9

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

K. Buchin, I. Kostitsyna, M. Löffler, R.I. Silveira

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

256 Downloads (Pure)

Abstract

In this paper we present new geometric algorithms for approximating the visibility between two imprecise locations amidst a set of obstacles, where the imprecise locations are modeled by continuous probability distributions. Our techniques are based on approximating distributions by a set of regions rather than on approximating by a discrete point sample. In this way we obtain guaranteed error bounds, and the results are more robust than similar results based on discrete point sets. We implemented our techniques and present an experimental evaluation. The experiments show that the actual error of our region-based approximation scheme converges quickly when increasing the complexity of the regions.

Original language	English
Title of host publication	Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX)
Editors	U. Brandes, D. Eppstein
Place of Publication	Philadelphia
Publisher	Society for Industrial and Applied Mathematics (SIAM)
Pages	94-103
ISBN (Print)	978-1-61197-375-4
DOIs	https://doi.org/10.1137/1.9781611973754.9
Publication status	Published - 2015
Event	17th Workshop on Algorithm Engineering and Experiments (ALENEX 2015) - Westin San Diego Gaslamp Quarter, San Diego, United States Duration: 5 Jan 2015 → 5 Jan 2015 Conference number: 17 http://www.siam.org/meetings/alenex15/

Workshop

Workshop	17th Workshop on Algorithm Engineering and Experiments (ALENEX 2015)
Abbreviated title	ALENEX '15
Country/Territory	United States
City	San Diego
Period	5/01/15 → 5/01/15
Other	Event co-located with the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '15) and the 12th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '15)
Internet address	http://www.siam.org/meetings/alenex15/

Access to Document

10.1137/1.9781611973754.9

final author versionFinal author version , 1.32 MB

Cite this

Buchin, K., Kostitsyna, I., Löffler, M., & Silveira, R. I. (2015). Region-based approximation of probability distributions (for visibility between imprecise points among obstacles). In U. Brandes, & D. Eppstein (Eds.), Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 94-103). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611973754.9

@inproceedings{873519ef4cf64d8bb35e33ec2592a96b,

title = "Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)",

abstract = "In this paper we present new geometric algorithms for approximating the visibility between two imprecise locations amidst a set of obstacles, where the imprecise locations are modeled by continuous probability distributions. Our techniques are based on approximating distributions by a set of regions rather than on approximating by a discrete point sample. In this way we obtain guaranteed error bounds, and the results are more robust than similar results based on discrete point sets. We implemented our techniques and present an experimental evaluation. The experiments show that the actual error of our region-based approximation scheme converges quickly when increasing the complexity of the regions.",

author = "K. Buchin and I. Kostitsyna and M. L{\"o}ffler and R.I. Silveira",

year = "2015",

doi = "10.1137/1.9781611973754.9",

language = "English",

isbn = "978-1-61197-375-4",

pages = "94--103",

editor = "U. Brandes and D. Eppstein",

booktitle = "Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX)",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

address = "United States",

note = "17th Workshop on Algorithm Engineering and Experiments (ALENEX 2015), ALENEX '15 ; Conference date: 05-01-2015 Through 05-01-2015",

url = "http://www.siam.org/meetings/alenex15/",

}

Buchin, K, Kostitsyna, I, Löffler, M & Silveira, RI 2015, Region-based approximation of probability distributions (for visibility between imprecise points among obstacles). in U Brandes & D Eppstein (eds), Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics (SIAM), Philadelphia, pp. 94-103, 17th Workshop on Algorithm Engineering and Experiments (ALENEX 2015), San Diego, California, United States, 5/01/15. https://doi.org/10.1137/1.9781611973754.9

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles). / Buchin, K.; Kostitsyna, I.; Löffler, M. et al.
Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX). ed. / U. Brandes; D. Eppstein. Philadelphia: Society for Industrial and Applied Mathematics (SIAM), 2015. p. 94-103.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

AU - Buchin, K.

AU - Kostitsyna, I.

AU - Löffler, M.

AU - Silveira, R.I.

N1 - Conference code: 17

PY - 2015

Y1 - 2015

N2 - In this paper we present new geometric algorithms for approximating the visibility between two imprecise locations amidst a set of obstacles, where the imprecise locations are modeled by continuous probability distributions. Our techniques are based on approximating distributions by a set of regions rather than on approximating by a discrete point sample. In this way we obtain guaranteed error bounds, and the results are more robust than similar results based on discrete point sets. We implemented our techniques and present an experimental evaluation. The experiments show that the actual error of our region-based approximation scheme converges quickly when increasing the complexity of the regions.

AB - In this paper we present new geometric algorithms for approximating the visibility between two imprecise locations amidst a set of obstacles, where the imprecise locations are modeled by continuous probability distributions. Our techniques are based on approximating distributions by a set of regions rather than on approximating by a discrete point sample. In this way we obtain guaranteed error bounds, and the results are more robust than similar results based on discrete point sets. We implemented our techniques and present an experimental evaluation. The experiments show that the actual error of our region-based approximation scheme converges quickly when increasing the complexity of the regions.

U2 - 10.1137/1.9781611973754.9

DO - 10.1137/1.9781611973754.9

M3 - Conference contribution

SN - 978-1-61197-375-4

SP - 94

EP - 103

BT - Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX)

A2 - Brandes, U.

A2 - Eppstein, D.

PB - Society for Industrial and Applied Mathematics (SIAM)

CY - Philadelphia

T2 - 17th Workshop on Algorithm Engineering and Experiments (ALENEX 2015)

Y2 - 5 January 2015 through 5 January 2015

ER -

Buchin K, Kostitsyna I, Löffler M, Silveira RI. Region-based approximation of probability distributions (for visibility between imprecise points among obstacles). In Brandes U, Eppstein D, editors, Proc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia: Society for Industrial and Applied Mathematics (SIAM). 2015. p. 94-103 doi: 10.1137/1.9781611973754.9

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Abstract

Workshop

Access to Document

Fingerprint

Cite this