Visibility maps of realistic terrains have linear smoothed complexity

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

Visibility maps of realistic terrains have linear smoothed complexity

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

149 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 language	English
Title of host publication	Abstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)
Pages	199-202
Publication status	Published - 2009

Access to Document

Metis233412Final published version, 689 KB

Cite this

@inproceedings{fe4078d43b4846ef901b35be4005a38c,

title = "Visibility maps of realistic terrains have linear smoothed complexity",

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.",

author = "{Berg, de}, M.T. and H.J. Haverkort and C.P. Tsirogiannis",

year = "2009",

language = "English",

pages = "199--202",

booktitle = "Abstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)",

}

TY - GEN

T1 - Visibility maps of realistic terrains have linear smoothed complexity

AU - Berg, de, M.T.

AU - Haverkort, H.J.

AU - Tsirogiannis, C.P.

PY - 2009

Y1 - 2009

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

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

M3 - Conference contribution

SP - 199

EP - 202

BT - Abstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)

ER -

Visibility maps of realistic terrains have linear smoothed complexity

Abstract

Access to Document

Fingerprint

Cite this