Triangles in space or Building (and analyzing) castles in the air

Boris Aronov; Micha Sharir

doi:10.1145/73393.73432

Triangles in space or Building (and analyzing) castles in the air

Boris Aronov, Micha Sharir

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

Abstract

We show that the combinatorial complexity of all non-convex cells in an arrangement of n (possibly intersecting) triangles in 3-space is O(n^7/3+δ), for any δ>0, and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement, analyze some special cases of the problem where improved bounds (and better algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.

Original language	English (US)
Title of host publication	Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
Publisher	Association for Computing Machinery, Inc
Pages	381-391
Number of pages	11
ISBN (Electronic)	0897912705, 9780897912709
DOIs	https://doi.org/10.1145/73393.73432
State	Published - Jan 6 1988
Event	4th Annual Symposium on Computational Geometry, SCG 1988 - Urbana-Champaign, United States Duration: Jun 6 1988 → Jun 8 1988

Publication series

Name	Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

Other

Other	4th Annual Symposium on Computational Geometry, SCG 1988
Country/Territory	United States
City	Urbana-Champaign
Period	6/6/88 → 6/8/88

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1145/73393.73432

Cite this

Triangles in space or Building (and analyzing) castles in the air. / Aronov, Boris; Sharir, Micha.
Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988. Association for Computing Machinery, Inc, 1988. p. 381-391 (Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988).

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

Aronov, B & Sharir, M 1988, Triangles in space or Building (and analyzing) castles in the air. in Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988. Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988, Association for Computing Machinery, Inc, pp. 381-391, 4th Annual Symposium on Computational Geometry, SCG 1988, Urbana-Champaign, United States, 6/6/88. https://doi.org/10.1145/73393.73432

@inproceedings{257aa46e4cec41f58ddc2ce2498593da,

title = "Triangles in space or Building (and analyzing) castles in the air",

abstract = "We show that the combinatorial complexity of all non-convex cells in an arrangement of n (possibly intersecting) triangles in 3-space is O(n7/3+δ), for any δ>0, and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement, analyze some special cases of the problem where improved bounds (and better algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.",

author = "Boris Aronov and Micha Sharir",

note = "Publisher Copyright: {\textcopyright} 1988 ACM.; 4th Annual Symposium on Computational Geometry, SCG 1988 ; Conference date: 06-06-1988 Through 08-06-1988",

year = "1988",

month = jan,

day = "6",

doi = "10.1145/73393.73432",

language = "English (US)",

series = "Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988",

publisher = "Association for Computing Machinery, Inc",

pages = "381--391",

booktitle = "Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988",

}

TY - GEN

T1 - Triangles in space or Building (and analyzing) castles in the air

AU - Aronov, Boris

AU - Sharir, Micha

PY - 1988/1/6

Y1 - 1988/1/6

N2 - We show that the combinatorial complexity of all non-convex cells in an arrangement of n (possibly intersecting) triangles in 3-space is O(n7/3+δ), for any δ>0, and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement, analyze some special cases of the problem where improved bounds (and better algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.

AB - We show that the combinatorial complexity of all non-convex cells in an arrangement of n (possibly intersecting) triangles in 3-space is O(n7/3+δ), for any δ>0, and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement, analyze some special cases of the problem where improved bounds (and better algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.

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

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

U2 - 10.1145/73393.73432

DO - 10.1145/73393.73432

M3 - Conference contribution

AN - SCOPUS:38049018141

T3 - Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

SP - 381

EP - 391

BT - Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

PB - Association for Computing Machinery, Inc

T2 - 4th Annual Symposium on Computational Geometry, SCG 1988

Y2 - 6 June 1988 through 8 June 1988

ER -

Triangles in space or Building (and analyzing) castles in the air

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this