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

DOI10.1007/S00453-019-00551-2zbMATH Open1421.68160arXiv1402.5681OpenAlexW2952063284WikidataQ128391289 ScholiaQ128391289MaRDI QIDQ2415360FDOQ2415360

Authors: Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira 

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Let $p$ and $q$ be two imprecise points, given as probability density functions on $mathbb{R}^2$, and let $calR$ be a set of $n$ line segments (obstacles) in $mathbb{R}^2$. We study the problem of approximating the probability that $p$ and $q$ can see each other; that is, that the segment connecting $p$ and $q$ does not cross any segment of $calR$. To solve this problem, we approximate each density function by a weighted set of polygons; a novel approach to dealing with probability density functions in computational geometry.

Full work available at URL: https://arxiv.org/abs/1402.5681

Recommendations

• Region-based approximation algorithms for visibility between imprecise locations
• Visibility testing and counting for uncertain segments
• Randomized approximation algorithms for planar visibility counting problem
• Visibility testing and counting
• On boundaries of highly visible spaces and applications.

zbMATH Keywords

Gaussian distributionprobability distributionvisibility in polygonal domains

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Computational geometry. Algorithms and applications.
• Constructing strongly convex approximate hulls with inaccurate primitives
• Shape Fitting on Point Sets with Probability Distributions
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Geometric Computations on Indecisive Points
• Title not available (Why is that?)
• Almost-Delaunay simplices, nearest neighbor relations for imprecise points
• Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)
• Region-based approximation algorithms for visibility between imprecise locations

Cited In (5)

• Peeling potatoes near-optimally in near-linear time
• Multiobserver multitarget visibility probabilities for poisson shadowing processes in the plane
• Region-based approximation algorithms for visibility between imprecise locations
• Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)
• Visibility testing and counting for uncertain segments

Uses Software

• Trio

This page was built for publication: Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415360)