TY - JOUR
T1 - Eliminating Depth Cycles Among Triangles in Three Dimensions
AU - Aronov, Boris
AU - Miller, Edward Y.
AU - Sharir, Micha
N1 - Funding Information:
Work on this paper by B.A. has been partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. Work by M.S. has been supported by Grant 2012/229 from the U.S.–Israel Binational Science Foundation, by Grants 892/13 and 260/18 from the Israel Science Foundation, by the Israeli Centers for Research Excellence (I-CORE) program (center no. 4/11), by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University, and by Grant G-1367-407.6/2016 from the German–Israeli Foundation for Scientific Research and Development. An earlier version of this work appeared in SODA’17 []
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/10/1
Y1 - 2020/10/1
N2 - The vertical depth relation among n pairwise openly disjoint triangles in 3-space may contain cycles. We show that, for any ε' 0 , the triangles can be cut into O(n3/2+ε) connected semialgebraic pieces, whose description complexity depends only on the choice of ε, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. The pieces can be constructed efficiently. This work extends the recent study by two of the authors (Discrete Comput. Geom. 59(3), 725–741 (2018)) on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth (Math. Proc. Camb. Philos. Soc. 159(3), 459–469 (2015)), which leads to a recursive algorithm for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result makes significant progress towards resolving a decades-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics. In addition, we generalize our bound to well-behaved patches of two-dimensional algebraic surfaces of constant degree.
AB - The vertical depth relation among n pairwise openly disjoint triangles in 3-space may contain cycles. We show that, for any ε' 0 , the triangles can be cut into O(n3/2+ε) connected semialgebraic pieces, whose description complexity depends only on the choice of ε, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. The pieces can be constructed efficiently. This work extends the recent study by two of the authors (Discrete Comput. Geom. 59(3), 725–741 (2018)) on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth (Math. Proc. Camb. Philos. Soc. 159(3), 459–469 (2015)), which leads to a recursive algorithm for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result makes significant progress towards resolving a decades-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics. In addition, we generalize our bound to well-behaved patches of two-dimensional algebraic surfaces of constant degree.
KW - Algebraic methods in combinatorial geometry
KW - Cycle elimination
KW - Depth cycles
KW - Depth order
KW - Painter’s algorithm
KW - Polynomial partitioning
UR - http://www.scopus.com/inward/record.url?scp=85087870534&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85087870534&partnerID=8YFLogxK
U2 - 10.1007/s00454-020-00221-z
DO - 10.1007/s00454-020-00221-z
M3 - Article
AN - SCOPUS:85087870534
SN - 0179-5376
VL - 64
SP - 627
EP - 653
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 3
ER -