Visibility maps of realistic terrains have linear smoothed complexity

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 θ(n²) 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). This provides an explanation why visibility maps of superlinear complexity are unlikely to be encountered in practice.

REFERENCES

• 1: Boris Aronov , Mark Berg , Shripad Thite, The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_9]
• 2: Siddhartha Chaudhuri , Vladlen Koltun, Smoothed analysis of probabilistic roadmaps, Computational Geometry: Theory and Applications, v.42 n.8, p.731-747, October, 2009 [doi>10.1016/j.comgeo.2008.10.005]
• 3: V. Damerow, F. Meyer auf der Heide, H. Racke, C. Scheideler, C. Sohler. Smoothed Motion Complexity. In ESA 2003, pp 161--171.
• 4: V. Damerow, C. Sohler. Extreme Points Under Random Noise. In ESA 2004, 264--274.
• 5: M. de Berg, A.F. van der Stappen, J. Vleugels, M.J. Katz. Realistic Input Models for Geometric Algorithms. Algorithmica, 34(1):81--97,2002.
• 6: Matthew J. Katz , Mark H. Overmars , Micha Sharir, Efficient hidden surface removal for objects with small union size, Computational Geometry: Theory and Applications, v.2 n.4, p.223-234, Dec. 1992 [doi>10.1016/0925-7721(92)90024-M]
• 7: M. de Berg, O. Cheong, H. Haverkort, J.G. Lim, L. Toma. I/O-efficient flow modeling on fat terrains. In WADS, pp 239--250, 2007.
• 8: G. Mandlburger, C. Briese. Using Airborne Laser Scanning for Improved Hydraulic Models. In International Congress on Modelling and Simulation 2007, pp 731--738.
• 9: E. Moet. Computation and Complexity of Visibility in Geometric Environments. PhD Thesis. Utrecht University 2008
• 10: Esther Moet , Marc van Kreveld , A. Frank van der Stappen, On realistic terrains, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137885]
• 11: Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]
• 12: D.A. Spielman. http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/index.html

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
realistic input, smoothed analysis, terrains, visibility maps