Computing the visibility map of fat objects

M. Berg, de, C.M. Gray

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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.
Original languageEnglish
Pages (from-to)410-418
JournalComputational Geometry
Volume43
Issue number4
DOIs
Publication statusPublished - 2010

Fingerprint Dive into the research topics of 'Computing the visibility map of fat objects'. Together they form a unique fingerprint.

Cite this