Visibility maps of realistic terrains have linear smoothed complexity
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 <em>n</em> triangles is <em>Θ</em>(<em>n</em><sup>2&...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2010-06-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/12 |
| _version_ | 1817998024678309888 |
|---|---|
| author | Mark de Berg Herman Haverkort Constantinos P. Tsirogiannis |
| author_facet | Mark de Berg Herman Haverkort Constantinos P. Tsirogiannis |
| author_sort | Mark de Berg |
| collection | DOAJ |
| description | 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 <em>n</em> triangles is <em>Θ</em>(<em>n</em><sup>2</sup>) 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 <em>Θ</em>(<em>n</em>). 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. |
| first_indexed | 2024-04-14T02:47:03Z |
| format | Article |
| id | doaj.art-82ff4ddfe0824755bb6f2f6a373805f6 |
| institution | Directory Open Access Journal |
| issn | 1920-180X |
| language | English |
| last_indexed | 2024-04-14T02:47:03Z |
| publishDate | 2010-06-01 |
| publisher | Carleton University |
| record_format | Article |
| series | Journal of Computational Geometry |
| spelling | doaj.art-82ff4ddfe0824755bb6f2f6a373805f62022-12-22T02:16:29ZengCarleton UniversityJournal of Computational Geometry1920-180X2010-06-011110.20382/jocg.v1i1a59Visibility maps of realistic terrains have linear smoothed complexityMark de Berg0Herman Haverkort1Constantinos P. Tsirogiannis2TU EindhovenTU EindhovenTU EindhovenWe 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 <em>n</em> triangles is <em>Θ</em>(<em>n</em><sup>2</sup>) 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 <em>Θ</em>(<em>n</em>). 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.http://jocg.org/index.php/jocg/article/view/12 |
| spellingShingle | Mark de Berg Herman Haverkort Constantinos P. Tsirogiannis Visibility maps of realistic terrains have linear smoothed complexity Journal of Computational Geometry |
| title | Visibility maps of realistic terrains have linear smoothed complexity |
| title_full | Visibility maps of realistic terrains have linear smoothed complexity |
| title_fullStr | Visibility maps of realistic terrains have linear smoothed complexity |
| title_full_unstemmed | Visibility maps of realistic terrains have linear smoothed complexity |
| title_short | Visibility maps of realistic terrains have linear smoothed complexity |
| title_sort | visibility maps of realistic terrains have linear smoothed complexity |
| url | http://jocg.org/index.php/jocg/article/view/12 |
| work_keys_str_mv | AT markdeberg visibilitymapsofrealisticterrainshavelinearsmoothedcomplexity AT hermanhaverkort visibilitymapsofrealisticterrainshavelinearsmoothedcomplexity AT constantinosptsirogiannis visibilitymapsofrealisticterrainshavelinearsmoothedcomplexity |