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 proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
79 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 languageEnglish
Title of host publicationProc. 17th Workshop on Algorithm Engineering and Experiments (ALENEX)
EditorsU. Brandes, D. Eppstein
Place of PublicationPhiladelphia
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages94-103
ISBN (Print)978-1-61197-375-4
DOIs
Publication statusPublished - 2015
Event17th Workshop on Algorithm Engineering and Experiments (ALENEX 2015) - Westin San Diego Gaslamp Quarter, San Diego, United States
Duration: 5 Jan 20155 Jan 2015
Conference number: 17
http://www.siam.org/meetings/alenex15/

Workshop

Workshop17th Workshop on Algorithm Engineering and Experiments (ALENEX 2015)
Abbreviated titleALENEX '15
CountryUnited States
CitySan Diego
Period5/01/155/01/15
OtherEvent 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

Fingerprint Dive into the research topics of 'Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)'. Together they form a unique fingerprint.

  • 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