Author(s): Mark de Berg | Herman Haverkort | Constantinos P. Tsirogiannis
Journal: Journal of Computational Geometry
ISSN 1920-180X
Volume: 1;
Issue: 1;
Start page: 57;
Date: 2010;
Original page
ABSTRACT
We study the complexity of the visibility map of terrains whose triangles are fat, not too steep and have roughly the same size. It is known that the complexity of the visibility map of such a terrain with n triangles is Θ(n2) in the worst case. We prove that if the elevations of the vertices of the terrain are subject to uniform noise which is proportional to the edge lengths, then the worst-case expected (smoothed) complexity is only Θ(n). We also prove non-trivial bounds for the smoothed complexity of instances where some triangles do not satisfy the above properties. Our results provide an explanation why visibility maps of superlinear complexity are unlikely to be encountered in practice.
Journal: Journal of Computational Geometry
ISSN 1920-180X
Volume: 1;
Issue: 1;
Start page: 57;
Date: 2010;
Original page
ABSTRACT
We study the complexity of the visibility map of terrains whose triangles are fat, not too steep and have roughly the same size. It is known that the complexity of the visibility map of such a terrain with n triangles is Θ(n2) in the worst case. We prove that if the elevations of the vertices of the terrain are subject to uniform noise which is proportional to the edge lengths, then the worst-case expected (smoothed) complexity is only Θ(n). We also prove non-trivial bounds for the smoothed complexity of instances where some triangles do not satisfy the above properties. Our results provide an explanation why visibility maps of superlinear complexity are unlikely to be encountered in practice.
