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

Kevin Buchin, Irina Kostitsyna (Corresponding author), Maarten Löffler, Rodrigo I. Silveira

Research output: Contribution to journalArticleAcademicpeer-review

39 Downloads (Pure)

Abstract

Let p and q be two imprecise points, given as probability density functions on R 2 , and let O be a set of disjoint polygonal obstacles in R 2 . We study the problem of approximating the probability that p and q can see each other; i.e., that the segment connecting p and q does not cross any obstacle in O. To solve this problem, we first approximate each density function by a weighted set of polygons. Then we focus on computing the visibility between two points inside two of such polygons, where we can assume that the points are drawn uniformly at random. We show how this problem can be solved exactly in O((n+ m) 2 ) time, where n and m are the total complexities of the two polygons and the set of obstacles, respectively. Using this as a subroutine, we show that the probability that p and q can see each other amidst a set of obstacles of total complexity m can be approximated within error ε in O(1 / ε 3 + m 2 / ε 2 ) time.

Original languageEnglish
Pages (from-to)2682–2715
Number of pages34
JournalAlgorithmica
Volume81
Issue number7
Early online date16 Feb 2019
DOIs
Publication statusPublished - 1 Jul 2019

Keywords

  • Gaussian distribution
  • Probability distribution
  • Visibility in polygonal domains

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