Visibility maps of realistic terrains have linear smoothed complexity

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

doi:10.1145/1542362.1542397

Visibility maps of realistic terrains have linear smoothed complexity

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

Algorithms

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

2 Citaten (Scopus)

Samenvatting

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 ¿(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 ¿(n). This provides an explanation why visibility maps of superlinear complexity are unlikely to be encountered in practice.

Originele taal-2	Engels
Titel	Proceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009)
Plaats van productie	New York NY
Uitgeverij	Association for Computing Machinery, Inc
Pagina's	163-168
ISBN van geprinte versie	978-1-60558-501-7
DOI's	https://doi.org/10.1145/1542362.1542397
Status	Gepubliceerd - 2009

Toegang tot document

10.1145/1542362.1542397

Citeer dit

@inproceedings{d6ae4e965b5c429b8dbaf96225c8bca2,

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

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 ¿(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 ¿(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",

doi = "10.1145/1542362.1542397",

language = "English",

isbn = "978-1-60558-501-7",

pages = "163--168",

booktitle = "Proceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

}

Visibility maps of realistic terrains have linear smoothed complexity. / Berg, de, M.T.; Haverkort, H.J.; Tsirogiannis, C.P.
Proceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009). New York NY: Association for Computing Machinery, Inc, 2009. blz. 163-168.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

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 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 ¿(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 ¿(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 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 ¿(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 ¿(n). This provides an explanation why visibility maps of superlinear complexity are unlikely to be encountered in practice.

U2 - 10.1145/1542362.1542397

DO - 10.1145/1542362.1542397

M3 - Conference contribution

SN - 978-1-60558-501-7

SP - 163

EP - 168

BT - Proceedings 25th Annual ACM Symposium on Computational Geometry (SoCG'09, Aarhus, Denmark, June 8-10, 2009)

PB - Association for Computing Machinery, Inc

CY - New York NY

ER -

Visibility maps of realistic terrains have linear smoothed complexity

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit