TY - JOUR

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

AU - Buchin, Kevin

AU - Kostitsyna, Irina

AU - Löffler, Maarten

AU - Silveira, Rodrigo I.

N1 - (to appear)

PY - 2019

Y1 - 2019

N2 - Let p and q be two imprecise points, given as probability density functions on R2, and let O be a set of disjoint polygonal obstacles in R2. 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+m2/ε2) time.

AB - Let p and q be two imprecise points, given as probability density functions on R2, and let O be a set of disjoint polygonal obstacles in R2. 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+m2/ε2) time.

KW - Visibility in polygonal domains

KW - Probability distribution

KW - Gaussian distribution

U2 - 10.1007/s00453-019-00551-2

DO - 10.1007/s00453-019-00551-2

M3 - Article

SN - 0178-4617

VL - 81

SP - 2682

EP - 2715

JO - Algorithmica

JF - Algorithmica

ER -