Unions of fat convex polytopes have short skeletons

Boris Aronov; Mark de Berg

doi:10.1007/s00454-012-9422-8

Unions of fat convex polytopes have short skeletons

Boris Aronov, Mark de Berg

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

Abstract

The skeleton of a polyhedral set is the union of its edges and vertices. Let P be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f _max be the maximum complexity of any face of a polytope in P. We prove that the total length of the skeleton of the union of the polytopes in P is at most O(α(n)· log * n · log f _max) times the sum of the skeleton lengths of the individual polytopes.

Original language	English (US)
Pages (from-to)	53-64
Number of pages	12
Journal	Discrete and Computational Geometry
Volume	48
Issue number	1
DOIs	https://doi.org/10.1007/s00454-012-9422-8
State	Published - Jul 2012

Keywords

Combinatorial complexity
Convex polytopes
Fat polytopes
Skeleton of union

ASJC Scopus subject areas

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

Access to Document

10.1007/s00454-012-9422-8

Cite this

@article{ba126b6f0a104a87a23249403dd0b40c,

title = "Unions of fat convex polytopes have short skeletons",

abstract = "The skeleton of a polyhedral set is the union of its edges and vertices. Let P be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in P. We prove that the total length of the skeleton of the union of the polytopes in P is at most O(α(n)· log * n · log f max) times the sum of the skeleton lengths of the individual polytopes.",

keywords = "Combinatorial complexity, Convex polytopes, Fat polytopes, Skeleton of union",

author = "Boris Aronov and {de Berg}, Mark",

note = "Funding Information: This research was supported by the Netherlands{\textquoteright} Organisation for Scientific Research (NWO) under project no. 639.023.301. Funding Information: Work by B.A. has been partially supported by a grant from the U.S.–Israel Binational Science Foundation, by NSA MSP Grant H98230-06-1-0016, and by NSF Grant CCF-08-30691. ",

year = "2012",

month = jul,

doi = "10.1007/s00454-012-9422-8",

language = "English (US)",

volume = "48",

pages = "53--64",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Unions of fat convex polytopes have short skeletons

AU - Aronov, Boris

AU - de Berg, Mark

N1 - Funding Information: This research was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. Funding Information: Work by B.A. has been partially supported by a grant from the U.S.–Israel Binational Science Foundation, by NSA MSP Grant H98230-06-1-0016, and by NSF Grant CCF-08-30691.

PY - 2012/7

Y1 - 2012/7

N2 - The skeleton of a polyhedral set is the union of its edges and vertices. Let P be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in P. We prove that the total length of the skeleton of the union of the polytopes in P is at most O(α(n)· log * n · log f max) times the sum of the skeleton lengths of the individual polytopes.

AB - The skeleton of a polyhedral set is the union of its edges and vertices. Let P be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in P. We prove that the total length of the skeleton of the union of the polytopes in P is at most O(α(n)· log * n · log f max) times the sum of the skeleton lengths of the individual polytopes.

KW - Combinatorial complexity

KW - Convex polytopes

KW - Fat polytopes

KW - Skeleton of union

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

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

U2 - 10.1007/s00454-012-9422-8

DO - 10.1007/s00454-012-9422-8

M3 - Article

AN - SCOPUS:84860887358

SN - 0179-5376

VL - 48

SP - 53

EP - 64

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Unions of fat convex polytopes have short skeletons

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this