@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",

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",

note = "4th Annual Symposium on Computational Geometry, SCG 1988 ; Conference date: 06-06-1988 Through 08-06-1988",

}