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

Boris Aronov; Otfried Cheong; Michael Gene Dobbins; Xavier Goaoc

doi:10.1007/s00454-016-9820-4

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

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, Xavier Goaoc

Research output: Contribution to journal › Article › peer-review

Abstract

We show that the union of n translates of a convex body in R³ can have Θ(n³) holes in the worst case, where a hole in a set X is a connected component of R³\ 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.

Original language	English (US)
Pages (from-to)	104-124
Number of pages	21
Journal	Discrete and Computational Geometry
Volume	57
Issue number	1
DOIs	https://doi.org/10.1007/s00454-016-9820-4
State	Published - Jan 1 2017

Keywords

Convex sets
Motion planning
Union complexity

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-016-9820-4

Cite this

@article{1cefa17a63584580bd747991445d361b,

title = "The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions",

abstract = "We show that the union of n translates of a convex body in R3 can have Θ(n3) holes in the worst case, where a hole in a set X is a connected component of R3\ 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.",

keywords = "Convex sets, Motion planning, Union complexity",

author = "Boris Aronov and Otfried Cheong and Dobbins, {Michael Gene} and Xavier Goaoc",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/s00454-016-9820-4",

language = "English (US)",

volume = "57",

pages = "104--124",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

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

AU - Aronov, Boris

AU - Cheong, Otfried

AU - Dobbins, Michael Gene

AU - Goaoc, Xavier

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We show that the union of n translates of a convex body in R3 can have Θ(n3) holes in the worst case, where a hole in a set X is a connected component of R3\ 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.

AB - We show that the union of n translates of a convex body in R3 can have Θ(n3) holes in the worst case, where a hole in a set X is a connected component of R3\ 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.

KW - Convex sets

KW - Motion planning

KW - Union complexity

UR - http://www.scopus.com/inward/record.url?scp=84988353079&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988353079&partnerID=8YFLogxK

U2 - 10.1007/s00454-016-9820-4

DO - 10.1007/s00454-016-9820-4

M3 - Article

AN - SCOPUS:84988353079

SN - 0179-5376

VL - 57

SP - 104

EP - 124

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this