Article

On realistic terrains

Authors:

Marc van Kreveld,

A. Frank van der StappenAuthors Info & Claims

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

Pages 177 - 186

https://doi.org/10.1145/1137856.1137885

Published: 05 June 2006 Publication History

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.

Digital Library

[2]

B. Aronov, A. Efrat, V. Koltun, and M. Sharir. On the union of κ-round objects in three and four dimensions. In Proc. 20st Annu. ACM Sympos. Comput. Geom., pages 383--390, 2004.

Digital Library

[3]

B. Aronov and J. O'Rourke. Nonoverlap of the star unfolding. Discrete Comput. Geom., 8:219--250, 1992.

Digital Library

[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.

Digital Library

[6]

M. de Berg. Vertical ray shooting for fat objects. In Proc. 21st Annu. ACM Sympos. Comput. Geom., pages 288--295, 2005.

Digital Library

[7]

M. de Berg, M. J. Katz, M. Overmars, A. F. van der Stappen, and J. Vleugels. Models and motion planning. Comput. Geom. Theory Appl., 23:53--68, 2002.

Digital Library

[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.

Digital Library

[9]

A. Efrat. The complexity of the union of (α, β)-covered objects. SIAM J. Comput., 34:775--787, 2005.

Digital Library

[10]

J. Erickson. Local polyhedra and geometric graphs. Comput. Geom. Theory Appl., 31:101--125, 2005.

Digital Library

[11]

S. Kapoor. Efficient computation of geodesic shortest paths. In Proc. 31st Annu. ACM Sympos. Theory of Computing, pages 770--779, 1999.

Digital Library

[12]

M. J. Katz, M. H. Overmars, and M. Sharir. Efficient hidden surface removal for objects with small union size. Comput. Geom. Theory Appl., 2:223--234, 1992.

Digital Library

[13]

J. Matoušek, J. Pach, M. Sharir, S. Sifrony, and E. Welzl. Fat triangles determine linearly many holes. SIAM J. Comput., 23:154--169, 1994.

Digital Library

[14]

M. McKenna. Worst-case optimal hidden-surface removal. ACM Trans. Graph., 6:19--28, 1987.

Digital Library

[15]

J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou. The discrete geodesic problem. SIAM J. Comput., 16:647--668, 1987.

Digital Library

[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]

M. H. Overmars and A. F. van der Stappen. Range searching and point location among fat objects. J. Algorithms, 21:629--656, 1996.

Digital Library

[18]

O. Schwarzkopf and J. Vleugels. Range searching in low-density environments. Inform. Process. Lett., 60:121--127, 1996.

Digital Library

[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]

M. van Kreveld. On fat partitioning, fat covering, and the union size of polygons. Comput. Geom. Theory Appl., 9(4):197--210, 1998.

Digital Library

[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.

Cited By

Liu YTang K(2013)The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfacesInformation Processing Letters10.1016/j.ipl.2012.12.010113:4(132-136)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ipl.2012.12.010
Bae SChwa K(2012)Farthest voronoi diagrams under travel time metricsProceedings of the 6th international conference on Algorithms and computation10.1007/978-3-642-28076-4_6(28-39)Online publication date: 15-Feb-2012
https://dl.acm.org/doi/10.1007/978-3-642-28076-4_6
Liu YChen ZTang K(2011)Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated SurfacesIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2010.22133:8(1502-1517)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1109/TPAMI.2010.221
Show More Cited By

Index Terms

On realistic terrains
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On realistic terrains

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, and a more general low-density assumption. We show that the visibility map of a point ...
Visibility maps of realistic terrains have linear smoothed complexity
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

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 ...
Computing $$L_1$$ Shortest Paths Among Polygonal Obstacles in the Plane
Abstract
Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, suppose a triangulation of the space outside the obstacles is given; we present an $$O(n+h\log h)$$ time and O(n) space algorithm for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

June 2006

500 pages

ISBN:1595933409

DOI:10.1145/1137856

Program Chairs:
Nina Amenta
University of California at Davis
,
Otfried Cheong
Korea Advanced Institute of Science and Technology

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG06

Sponsor:

SoCG06: 22nd Annual Symposium on Computational Geometry

June 5 - 7, 2006

Arizona, Sedona, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
356
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YTang K(2013)The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfacesInformation Processing Letters10.1016/j.ipl.2012.12.010113:4(132-136)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ipl.2012.12.010
Bae SChwa K(2012)Farthest voronoi diagrams under travel time metricsProceedings of the 6th international conference on Algorithms and computation10.1007/978-3-642-28076-4_6(28-39)Online publication date: 15-Feb-2012
https://dl.acm.org/doi/10.1007/978-3-642-28076-4_6
Liu YChen ZTang K(2011)Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated SurfacesIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2010.22133:8(1502-1517)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1109/TPAMI.2010.221
Schreiber Y(2010)An Optimal-Time Algorithm for Shortest Paths on Realistic PolyhedraDiscrete & Computational Geometry10.5555/3116259.311637543:1(21-53)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/3116259.3116375
Ahmed MDas SLodha SLubiw AMaheshwari ARoy S(2010)Approximation algorithms for shortest descending paths in terrainsJournal of Discrete Algorithms10.1016/j.jda.2009.05.0018:2(214-230)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.jda.2009.05.001
Cabello SFort MSellarès J(2009)Higher-order Voronoi diagrams on triangulated surfacesInformation Processing Letters10.5555/1517855.1518094109:9(440-445)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.5555/1517855.1518094
de Berg MHaverkort HTsirogiannis CHershberger JFogel E(2009)Visibility maps of realistic terrains have linear smoothed complexityProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542397(163-168)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542397
Schreiber Y(2009)An Optimal-Time Algorithm for Shortest Paths on Realistic PolyhedraDiscrete & Computational Geometry10.1007/s00454-009-9136-843:1(21-53)Online publication date: 30-Jan-2009
https://doi.org/10.1007/s00454-009-9136-8
Gray CLöffler MSilveira R(2009)Smoothing Imprecise 1.5D TerrainsApproximation and Online Algorithms10.1007/978-3-540-93980-1_17(214-226)Online publication date: 13-Jan-2009
https://dl.acm.org/doi/10.1007/978-3-540-93980-1_17
Moet Evan Kreveld Mvan der Stappen A(2008)On realistic terrainsComputational Geometry: Theory and Applications10.1016/j.comgeo.2007.10.00841:1-2(48-67)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1016/j.comgeo.2007.10.008
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents