Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira

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....

Mô tả chi tiết

Lưu vào:

Hiển thị chi tiết
Tác giả chính:	Buchin, Kevin, Kostitsyna, Irina, Löffler, Maarten, Silveira, Rodrigo I.
Đồng tác giả:	Kostitsyna, Irina
Định dạng:	text
Ngôn ngữ:	vie
Thông tin xuất bản:	Kostitsyna, Irina
Chủ đề:	Gaussian distribution Probability distribution Visibility in polygonal domains
Truy cập trực tuyến:	http://elib.ntt.edu.vn/Opac/DmdInfo.aspx?dmd_id=15606
Từ khóa:	Thêm từ khóa bạn đọc Không có từ khóa, Hãy là người đầu tiên gắn từ khóa cho biểu ghi này!

id	ntt-http:--elib.ntt.edu.vn-Opac-DmdInfo.aspx?dmd_id=15606
record_format	dspace
institution	Trường Đại học Nguyễn Tất Thành
collection	Kipos
language	vie
topic	Gaussian distribution Probability distribution Visibility in polygonal domains
spellingShingle	Gaussian distribution Probability distribution Visibility in polygonal domains Buchin, Kevin Kostitsyna, Irina Löffler, Maarten Silveira, Rodrigo I. Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
description	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 ﬁrstapproximate 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.
author2	Kostitsyna, Irina
author_facet	Kostitsyna, Irina Buchin, Kevin Kostitsyna, Irina Löffler, Maarten Silveira, Rodrigo I.
format	text
author	Buchin, Kevin Kostitsyna, Irina Löffler, Maarten Silveira, Rodrigo I.
author_sort	Buchin, Kevin
title	Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
title_short	Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
title_full	Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
title_fullStr	Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
title_full_unstemmed	Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira
title_sort	region-based approximation of probability distributions : for visibility between imprecise points among obstacles / kevin buchin, irina kostitsyna, maarten löffler, rodrigo i. silveira
publisher	Kostitsyna, Irina
url	http://elib.ntt.edu.vn/Opac/DmdInfo.aspx?dmd_id=15606
work_keys_str_mv	AT buchinkevin regionbasedapproximationofprobabilitydistributionsforvisibilitybetweenimprecisepointsamongobstacleskevinbuchinirinakostitsynamaartenlofflerrodrigoisilveira AT kostitsynairina regionbasedapproximationofprobabilitydistributionsforvisibilitybetweenimprecisepointsamongobstacleskevinbuchinirinakostitsynamaartenlofflerrodrigoisilveira AT lofflermaarten regionbasedapproximationofprobabilitydistributionsforvisibilitybetweenimprecisepointsamongobstacleskevinbuchinirinakostitsynamaartenlofflerrodrigoisilveira AT silveirarodrigoi regionbasedapproximationofprobabilitydistributionsforvisibilitybetweenimprecisepointsamongobstacleskevinbuchinirinakostitsynamaartenlofflerrodrigoisilveira
_version_	1806807440036986880

Region-Based Approximation of Probability Distributions : for Visibility Between Imprecise Points Among Obstacles / Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira

Tài liệu tương tự