Samenvatting
We give an output-sensitive algorithm for computing the visibility map of a set of n constant-complexity convex fat polyhedra or curved objects in 3-space. Our algorithm runs in O((n¿+¿k) polylog n) time, where k is the combinatorial complexity of the visibility map. This is the first algorithm for computing the visibility map of fat objects that does not require a depth order on the objects and is faster than the best known algorithm for general objects. It is also the first output-sensitive algorithm for curved objects that does not require a depth order.
Originele taal-2 | Engels |
---|---|
Titel | Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada |
Redacteuren | F. Dehne, J.R. Sack, N. Zeh |
Plaats van productie | Berlin |
Uitgeverij | Springer |
Pagina's | 251-262 |
ISBN van geprinte versie | 978-3-540-73948-7 |
DOI's | |
Status | Gepubliceerd - 2007 |
Evenement | 10th International Symposium on Algorithms and Data Structures (WADS 2007) - Halifax, Canada Duur: 15 aug. 2007 → 17 aug. 2007 Congresnummer: 10 |
Publicatie series
Naam | Lecture Notes in Computer Science |
---|---|
Volume | 4619 |
ISSN van geprinte versie | 0302-9743 |
Congres
Congres | 10th International Symposium on Algorithms and Data Structures (WADS 2007) |
---|---|
Verkorte titel | WADS 2007 |
Land/Regio | Canada |
Stad | Halifax |
Periode | 15/08/07 → 17/08/07 |
Ander | WADS 2007, Halifax, Nova Scotia, Canada |