Region-based Approximation Algorithms for Visibility between Imprecise Locations
Kevin Buchin, Irina Kostitsyna, Maarten Löffler, Rodrigo I. Silveira · Society for Industrial and Applied Mathematics eBooks · 2014
In this paper we present new geometric algorithms for approximating the visibility between two imprecise locations amidst a set of obstacles, where the imprecise locations are modeled by continuous probability distributions. Our techniques are based on approximating distributions by a set of regions rather than on approximating by a discrete point sample. In this way we obtain guaranteed error bounds, and the results are more robust than similar results based on discrete point sets. We implemented our techniques and present an experimental evaluation. The experiments show that the actual error of our region-based approximation scheme converges quickly when increasing the complexity of the regions.