Visibility maps of realistic terrains have linear smoothed complexity

M.T. Berg, de, H.J. Haverkort, C.P. Tsirogiannis

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

1 Citation (Scopus)
86 Downloads (Pure)

Abstract

We study the complexity of the visibility map of so-called realistic terrains: 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 T(n2) 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 T(n). This provides an explanation why visibility maps of superlinear complexity are unlikely to be encountered in practice.
Original languageEnglish
Title of host publicationAbstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)
Pages199-202
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'Visibility maps of realistic terrains have linear smoothed complexity'. Together they form a unique fingerprint.

Cite this