The union of convex polyhedra in three dimensions

Boris Aronov; Micha Sharir; Boaz Tagansky

doi:10.1137/S0097539793250755

The union of convex polyhedra in three dimensions

Boris Aronov, Micha Sharir, Boaz Tagansky

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

Abstract

We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k³ + kn log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with Ω(k³ + knα(k)) union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k³ + kn log k log n) expected time.

Original language	English (US)
Pages (from-to)	1670-1688
Number of pages	19
Journal	SIAM Journal on Computing
Volume	26
Issue number	6
DOIs	https://doi.org/10.1137/S0097539793250755
State	Published - Dec 1997

Keywords

Combinatorial complexity
Combinatorial geometry
Computational geometry
Convex polyhedra
Geometric algorithms
Randomized algorithms

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539793250755

Cite this

@article{2be3fed28fb741b9a4c27c3dc2c7a1fa,

title = "The union of convex polyhedra in three dimensions",

abstract = "We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k3 + kn log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with Ω(k3 + knα(k)) union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3 + kn log k log n) expected time.",

keywords = "Combinatorial complexity, Combinatorial geometry, Computational geometry, Convex polyhedra, Geometric algorithms, Randomized algorithms",

author = "Boris Aronov and Micha Sharir and Boaz Tagansky",

year = "1997",

month = dec,

doi = "10.1137/S0097539793250755",

language = "English (US)",

volume = "26",

pages = "1670--1688",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

T1 - The union of convex polyhedra in three dimensions

AU - Aronov, Boris

AU - Sharir, Micha

AU - Tagansky, Boaz

PY - 1997/12

Y1 - 1997/12

N2 - We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k3 + kn log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with Ω(k3 + knα(k)) union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3 + kn log k log n) expected time.

AB - We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k3 + kn log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with Ω(k3 + knα(k)) union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3 + kn log k log n) expected time.

KW - Combinatorial complexity

KW - Combinatorial geometry

KW - Computational geometry

KW - Convex polyhedra

KW - Geometric algorithms

KW - Randomized algorithms

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

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

U2 - 10.1137/S0097539793250755

DO - 10.1137/S0097539793250755

M3 - Article

AN - SCOPUS:0000045918

SN - 0097-5397

VL - 26

SP - 1670

EP - 1688

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

The union of convex polyhedra in three dimensions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this