Union of convex polyhedra in three dimensions

Boris Aronov; Micha Sharir

Union of convex polyhedra in three dimensions

Boris Aronov, Micha Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k³+kn log³ k) expected time.

Original language	English (US)
Title of host publication	Annual Symposium on Foundatons of Computer Science (Proceedings)
Editors	Anon
Publisher	Publ by IEEE
Pages	518-527
Number of pages	10
ISBN (Print)	0818643706
State	Published - 1993
Event	Proceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA Duration: Nov 3 1993 → Nov 5 1993

Publication series

Name	Annual Symposium on Foundatons of Computer Science (Proceedings)
ISSN (Print)	0272-5428

Other

Other	Proceedings of the 34th Annual Symposium on Foundations of Computer Science
City	Palo Alto, CA, USA
Period	11/3/93 → 11/5/93

ASJC Scopus subject areas

Hardware and Architecture

Cite this

@inproceedings{10b8ea1cf39c4ebe9b9e3c5801e63016,

title = "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 log2 k). This bound is almost tight in the worst case. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3+kn log3 k) expected time.",

author = "Boris Aronov and Micha Sharir",

year = "1993",

language = "English (US)",

isbn = "0818643706",

series = "Annual Symposium on Foundatons of Computer Science (Proceedings)",

publisher = "Publ by IEEE",

pages = "518--527",

editor = "Anon",

booktitle = "Annual Symposium on Foundatons of Computer Science (Proceedings)",

note = "Proceedings of the 34th Annual Symposium on Foundations of Computer Science ; Conference date: 03-11-1993 Through 05-11-1993",

}

TY - GEN

T1 - Union of convex polyhedra in three dimensions

AU - Aronov, Boris

AU - Sharir, Micha

PY - 1993

Y1 - 1993

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 log2 k). This bound is almost tight in the worst case. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3+kn log3 k) 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 log2 k). This bound is almost tight in the worst case. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3+kn log3 k) expected time.

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

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

M3 - Conference contribution

AN - SCOPUS:0027842565

SN - 0818643706

T3 - Annual Symposium on Foundatons of Computer Science (Proceedings)

SP - 518

EP - 527

BT - Annual Symposium on Foundatons of Computer Science (Proceedings)

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the 34th Annual Symposium on Foundations of Computer Science

Y2 - 3 November 1993 through 5 November 1993

ER -

Union of convex polyhedra in three dimensions

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this