Computing the visibility map of fat objects

M. Berg, de; C.M. Gray

doi:10.1016/j.comgeo.2008.12.010

Computing the visibility map of fat objects

M. Berg, de, C.M. Gray

Algorithms

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	410-418
Journal	Computational Geometry
Volume	43
Issue number	4
DOIs	https://doi.org/10.1016/j.comgeo.2008.12.010
Publication status	Published - 2010

Access to Document

10.1016/j.comgeo.2008.12.010

Cite this

@article{0221c6ee3cda46cabcc5b0cd75919d8c,

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 = "2010",

doi = "10.1016/j.comgeo.2008.12.010",

language = "English",

volume = "43",

pages = "410--418",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Computing the visibility map of fat objects

AU - Berg, de, M.

AU - Gray, C.M.

PY - 2010

Y1 - 2010

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.1016/j.comgeo.2008.12.010

DO - 10.1016/j.comgeo.2008.12.010

M3 - Article

SN - 0925-7721

VL - 43

SP - 410

EP - 418

JO - Computational Geometry

JF - Computational Geometry

IS - 4

ER -

Computing the visibility map of fat objects

Abstract

Access to Document

Fingerprint

Cite this