The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 522
  • Download : 0
We show that the union of n translates of a convex body in R-3 can have Theta (n(3)) holes in the worst case, where a hole in a set X is a connected component of R-3 \ X. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.
Publisher
SPRINGER
Issue Date
2017-01
Language
English
Article Type
Article
Keywords

VORONOI DIAGRAMS; COMPLEXITY

Citation

DISCRETE & COMPUTATIONAL GEOMETRY, v.57, no.1, pp.104 - 124

ISSN
0179-5376
DOI
10.1007/s00454-016-9820-4
URI
http://hdl.handle.net/10203/222774
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0