research-article

Visibility maps of realistic terrains have linear smoothed complexity

Authors:

Mark de Berg,

Herman Haverkort,

Constantinos P. TsirogiannisAuthors Info & Claims

SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

Pages 163 - 168

https://doi.org/10.1145/1542362.1542397

Published: 08 June 2009 Publication History

Get Access

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]

B. Aronov, M. de Berg, S. Thite. The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains. In ESA 2008, pp 100--111.

Digital Library

Google Scholar

[2]

S. Chauduri, V. Koltun. Smoothed analysis of probabilistic roadmaps. Computational Geometry: Theory and Applications, to appear.

Digital Library

Google Scholar

[3]

V. Damerow, F. Meyer auf der Heide, H. Racke, C. Scheideler, C. Sohler. Smoothed Motion Complexity. In ESA 2003, pp 161--171.

Google Scholar

[4]

V. Damerow, C. Sohler. Extreme Points Under Random Noise. In ESA 2004, 264--274.

Google Scholar

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

Digital Library

Google Scholar

[6]

M.J. Katz, M.H. Overmars, M. Sharir. Efficient Hidden Surface Removal for Objects with Small Union Size. Comput. Geom., 2:223--234,1992.

Digital Library

Google Scholar

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

Digital Library

Google Scholar

[8]

G. Mandlburger, C. Briese. Using Airborne Laser Scanning for Improved Hydraulic Models. In International Congress on Modelling and Simulation 2007, pp 731--738.

Google Scholar

[9]

E. Moet. Computation and Complexity of Visibility in Geometric Environments. PhD Thesis. Utrecht University 2008

Google Scholar

[10]

E. Moet, M. van Kreveld, A.F. van der Stappen. On realistic terrains. In SoCG 2006, pp 177--186.

Digital Library

Google Scholar

[11]

D.A. Spielman, Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385--463, 2004.

Digital Library

Google Scholar

[12]

D.A. Spielman. http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/index.html

Google Scholar

Cited By

View all

Devillers OGlisse MGoaoc Xda Fonseca GLewiner TPeñaranda LChan TKlein R(2013)Complexity analysis of random geometric structures made simplerProceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462362(167-176)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2462356.2462362

Index Terms

Visibility maps of realistic terrains have linear smoothed complexity
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

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

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 ...
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 ...
On the expected complexity of voronoi diagrams on terrains
SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et.al. [abt-cbvdrt-08] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

June 2009

426 pages

ISBN:9781605585017

DOI:10.1145/1542362

Program Chairs:
John Hershberger
Mentor Graphics Corp.
,
Efi Fogel
Tel Aviv University

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '09

Sponsor:

SoCG '09: 25th Annual Symposium on Computational Geometry

June 8 - 10, 2009

Aarhus, Denmark

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
188
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Devillers OGlisse MGoaoc Xda Fonseca GLewiner TPeñaranda LChan TKlein R(2013)Complexity analysis of random geometric structures made simplerProceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462362(167-176)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2462356.2462362

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.

Cited By

Index Terms

Recommendations

On realistic terrains

On realistic terrains

On the expected complexity of voronoi diagrams on terrains