Computing the visibility map of fat objects

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	https://doi.org/10.1007/978-3-540-73951-7_23
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

Toegang tot document

10.1007/978-3-540-73951-7_23

Metis210765Definitieve gepubliceerde versie, 445 KB

Citeer dit

Berg, de, M., & Gray, C. M. (2007). Computing the visibility map of fat objects. In F. Dehne, J. R. Sack, & N. Zeh (editors), Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada (blz. 251-262). (Lecture Notes in Computer Science; Vol. 4619). Springer. https://doi.org/10.1007/978-3-540-73951-7_23

@inproceedings{2f317dadfa354b99ac46c3d515cbcdd2,

title = "Computing the visibility map of fat objects",

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

author = "{Berg, de}, M. and C.M. Gray",

year = "2007",

doi = "10.1007/978-3-540-73951-7_23",

language = "English",

isbn = "978-3-540-73948-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "251--262",

editor = "F. Dehne and J.R. Sack and N. Zeh",

booktitle = "Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada",

note = "10th International Symposium on Algorithms and Data Structures (WADS 2007), WADS 2007 ; Conference date: 15-08-2007 Through 17-08-2007",

}

Berg, de, M & Gray, CM 2007, Computing the visibility map of fat objects. in F Dehne, JR Sack & N Zeh (uitgave), Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. Lecture Notes in Computer Science, vol. 4619, Springer, Berlin, blz. 251-262, 10th International Symposium on Algorithms and Data Structures (WADS 2007), Halifax, Nova Scotia, Canada, 15/08/07. https://doi.org/10.1007/978-3-540-73951-7_23

Computing the visibility map of fat objects. / Berg, de, M.; Gray, C.M.
Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. uitgave / F. Dehne; J.R. Sack; N. Zeh. Berlin: Springer, 2007. blz. 251-262 (Lecture Notes in Computer Science; Vol. 4619).

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

TY - GEN

T1 - Computing the visibility map of fat objects

AU - Berg, de, M.

AU - Gray, C.M.

N1 - Conference code: 10

PY - 2007

Y1 - 2007

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

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

U2 - 10.1007/978-3-540-73951-7_23

DO - 10.1007/978-3-540-73951-7_23

M3 - Conference contribution

SN - 978-3-540-73948-7

T3 - Lecture Notes in Computer Science

SP - 251

EP - 262

BT - Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada

A2 - Dehne, F.

A2 - Sack, J.R.

A2 - Zeh, N.

PB - Springer

CY - Berlin

T2 - 10th International Symposium on Algorithms and Data Structures (WADS 2007)

Y2 - 15 August 2007 through 17 August 2007

ER -

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit