TRA CỨU
thông tin biểu ghi
  • Bài trích
  • Nhan đề: Region-Based Approximation of Probability Distributions :
Tác giả CN Buchin, Kevin
Nhan đề Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
Tóm tắt 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 ofapproximating the probability that p and q can see each other; i.e., that the segmentconnecting p and q does not cross any obstacle in O. To solve this problem, we firstapproximate each density function by a weighted set of polygons. Then we focus oncomputing the visibility between two points inside two of such polygons, where wecan assume that the points are drawn uniformly at random. We show how this problemcan be solved exactly in O((n + m)2) time, where n and m are the total complexitiesof 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 obstaclesof total complexity m can be approximated within error ε in O(1/ε3 + m2/ε2) time.
Từ khóa tự do Gaussian distribution
Từ khóa tự do Probability distribution
Từ khóa tự do Visibility in polygonal domains
Tác giả(bs) CN Kostitsyna, Irina
Tác giả(bs) CN Löffler, Maarten
Tác giả(bs) CN Silveira, Rodrigo I.
Nguồn trích AlgorithmicaSpringer USVol. 81, Issue 7 (Jul. 2019) p.2682-2715
000 00000nab#a2200000ui#4500
00115606
0029
0046846B1EC-9301-4DAC-8AB6-0FB84BAD73D1
005201906170939
008081223s2019 vm| vie
0091 0
039|a20190617093947|bquyennt|y20190617093921|zquyennt
100 |aBuchin, Kevin
245 |aRegion-Based Approximation of Probability Distributions : |bfor Visibility Between Imprecise Points Among Obstacles / |cKevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
520 |aLet 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 ofapproximating the probability that p and q can see each other; i.e., that the segmentconnecting p and q does not cross any obstacle in O. To solve this problem, we firstapproximate each density function by a weighted set of polygons. Then we focus oncomputing the visibility between two points inside two of such polygons, where wecan assume that the points are drawn uniformly at random. We show how this problemcan be solved exactly in O((n + m)2) time, where n and m are the total complexitiesof 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 obstaclesof total complexity m can be approximated within error ε in O(1/ε3 + m2/ε2) time.
653 |aGaussian distribution
653 |aProbability distribution
653 |aVisibility in polygonal domains
700 |aKostitsyna, Irina
700 |aLöffler, Maarten
700 |aSilveira, Rodrigo I.
773 |tAlgorithmica|dSpringer US|gVol. 81, Issue 7 (Jul. 2019) p.2682-2715
890|a0|b0|c0|d0
Không tìm thấy biểu ghi nào

Không có liên kết tài liệu số nào