On realistic terrains

ABSTRACT

We study worst-case complexities of visibility and distance structures on terrains under realistic assumptions on edge length ratios and the angles of the triangles. We show that the visibility map of a point for a realistic terrain with n triangles has complexity Θ(n√n). We also prove that the shortest path between two points p and q on a realistic terrain passes through Θ(√n) triangles, and that the bisector between p and q has complexity O(n √n). We use these results to show that the shortest path map for any point on a realistic terrain has complexity Θ(n√n), and that the Voronoi diagram for any set of m points on a realistic terrain has complexity Ω(n + m√n) and O((n+m)√n). Our results immediately imply more efficient algorithms for computing the various structures on realistic terrains.

REFERENCES

• 1: H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig. Approximate motion planning and the complexity of the boundary of the union of simple geometric figures. Algorithmica, 8:391--406, 1992.
• 2: B. Aronov , A. Efrat , V. Koltun , Micha Sharir, On the union of κ-round objects, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997875]
• 3: Boris Aronov , Joseph O'Rourke, Nonoverlap of the star unfolding, Discrete & Computational Geometry, v.8 n.3, p.219-250, 1992
• 4: J. Chen and Y. Han. Shortest paths on a polyhedron. Internat. J. Comput. Geom. Appl., 6(2):127--144, 1996.
• 5: M. de Berg. Linear size binary space partitions for uncluttered scenes. Algorithmica, 28:353--366, 2000.
• 6: Mark de Berg, Vertical ray shooting for fat objects, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064137]
• 7: Mark de Berg , Matthew J. Katz , Mark H. Overmars , A. Frank van der Stappen , Jules Vleugels, Models and motion planning, Computational Geometry: Theory and Applications, v.23 n.1, p.53-68, July 2002 [doi>10.1016/S0925-7721(01)00022-0 ]
• 8: M. de Berg, M. J. Katz, A. F. van der Stappen, and J. Vleugels. Realistic input models for geometric algorithms. Algorithmica, 34:81--97, 2002.
• 9: Alon Efrat, The Complexity of the Union of $(\alpha,\beta)$-Covered Objects, SIAM Journal on Computing, v.34 n.4, p.775-787, 2005 [doi>10.1137/S0097539702407515]
• 10: Jeff Erickson, Local polyhedra and geometric graphs, Computational Geometry: Theory and Applications, v.31 n.1-2, p.101-125, May 2005 [doi>10.1016/j.comgeo.2004.08.004]
• 11: Sanjiv Kapoor, Efficient computation of geodesic shortest paths, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.770-779, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301449]
• 12: 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 ]
• 13: Jiri Matousek , Janos Pach , Micha Sharir , Shmuel Sifrony , Emo Welzl, Fat Triangles Determine Linearly Many Holes, SIAM Journal on Computing, v.23 n.1, p.154-169, Feb. 1994 [doi>10.1137/S009753979018330X]
• 14: Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
• 15: Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
• 16: J. S. B. Mitchell, D. M. Mount, and S. Suri. Query-sensitive ray shooting. Internat. J. Comput. Geom. Appl., 7(4):317--347, Aug. 1997.
• 17: Mark H. Overmars , A. Frank van der Stappen, Range searching and point location among fat objects, Journal of Algorithms, v.21 n.3, p.629-656, Nov. 1996 [doi>10.1006/jagm.1996.0063 ]
• 18: Otfried Schwarzkopf , Jules Vleugels, Range searching in low-density environments, Information Processing Letters, v.60 n.3, p.121-127, Nov. 11, 1996 [doi>10.1016/S0020-0190(96)00154-8 ]
• 19: A. F. van der Stappen, M. H. Overmars, M. de Berg, and J. Vleugels. Motion planning in environments with low obstacle density. Discrete Comput. Geom., 20(4):561--587, 1998.
• 20: Marc van Kreveld, On fat partitioning, fat covering and the union size of polygons, Computational Geometry: Theory and Applications, v.9 n.4, p.197-210, March 1998 [doi>10.1016/S0925-7721(96)00016-8 ]
• 21: J. Vleugels. On Fatness and Fitness—Realistic Input Models for Geometric Algorithms. Ph.{D. thesis, Dept. Comput. Sci., Univ. Utrecht, Utrecht, The Netherlands, 1997.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
polyhedral terrains, realistic input models, shortest paths, visibility maps, voronoi diagrams