Eliminating depth cycles among triangles in three dimensions

Boris Aronov, Edward Y. Miller, Micha Sharir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any " > 0, the triangles can be cut into O(n3=2+ϵ) pieces, where each piece is a connected semi-algebraic set 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. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors 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, which leads to a recursive procedure 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 essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
PublisherAssociation for Computing Machinery
Pages2476-2494
Number of pages19
ISBN (Electronic)9781611974782
StatePublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain

Other

Other28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
CountrySpain
CityBarcelona
Period1/16/171/19/17

Fingerprint

Computational geometry
Computer graphics
Algebra
Topology
Polynomials
Removal
Triangle
Cycle
Semi-algebraic sets
Connected set
Partial order
Three-dimension
Pairwise
Partitioning
Open problems
Disjoint
Vertical
Polynomial

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Aronov, B., Miller, E. Y., & Sharir, M. (2017). Eliminating depth cycles among triangles in three dimensions. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 2476-2494). Association for Computing Machinery.

Eliminating depth cycles among triangles in three dimensions. / Aronov, Boris; Miller, Edward Y.; Sharir, Micha.

28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Association for Computing Machinery, 2017. p. 2476-2494.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Aronov, B, Miller, EY & Sharir, M 2017, Eliminating depth cycles among triangles in three dimensions. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Association for Computing Machinery, pp. 2476-2494, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, 16-19 January.
Aronov B, Miller EY, Sharir M. Eliminating depth cycles among triangles in three dimensions. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Association for Computing Machinery. 2017. p. 2476-2494.

Aronov, Boris; Miller, Edward Y.; Sharir, Micha / Eliminating depth cycles among triangles in three dimensions.

28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Association for Computing Machinery, 2017. p. 2476-2494.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

@inbook{e53e2bfb03ec4583b1c32011750f75bf,
title = "Eliminating depth cycles among triangles in three dimensions",
abstract = "Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any {"} > 0, the triangles can be cut into O(n3=2+ϵ) pieces, where each piece is a connected semi-algebraic set 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. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors 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, which leads to a recursive procedure 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 essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.",
author = "Boris Aronov and Miller, {Edward Y.} and Micha Sharir",
year = "2017",
pages = "2476--2494",
booktitle = "28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017",
publisher = "Association for Computing Machinery",

}

TY - CHAP

T1 - Eliminating depth cycles among triangles in three dimensions

AU - Aronov,Boris

AU - Miller,Edward Y.

AU - Sharir,Micha

PY - 2017

Y1 - 2017

N2 - Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any " > 0, the triangles can be cut into O(n3=2+ϵ) pieces, where each piece is a connected semi-algebraic set 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. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors 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, which leads to a recursive procedure 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 essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

AB - Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any " > 0, the triangles can be cut into O(n3=2+ϵ) pieces, where each piece is a connected semi-algebraic set 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. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors 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, which leads to a recursive procedure 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 essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

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

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

M3 - Conference contribution

SP - 2476

EP - 2494

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

PB - Association for Computing Machinery

ER -