Almost tight bounds for eliminating depth cycles in three dimensions

DOI10.1007/s00454-017-9920-9zbMath1390.68703arXiv1512.00358OpenAlexW2751884597MaRDI QIDQ1745206

Micha Sharir, Boris Aronov

Publication date: 20 April 2018

Published in: Discrete \& Computational Geometry, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.00358

zbMATH Keywords

computational geometrypolynomial partitioningcycle eliminationlines in spacealgebraic methods in combinatorial geometrydepth cyclesdepth orderPainter's algorithmpolynomial partitionpainter's algorithm

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Combinatorial complexity of geometric structures (52C45)

Related Items (7)

Counting and Cutting Rich Lenses in Arrangements of Circles ⋮ Cutting algebraic curves into pseudo-segments and applications ⋮ Eliminating depth cycles among triangles in three dimensions ⋮ Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications ⋮ Removing depth-order cycles among triangles: an algorithm generating triangular fragments ⋮ Almost tight bounds for eliminating depth cycles in three dimensions ⋮ Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Erdős distinct distances problem in the plane
• On lines and joints
• Counting and cutting cycles of lines and rods in space
• Almost tight bounds for eliminating depth cycles in three dimensions
• Cutting algebraic curves into pseudo-segments and applications
• Divide-and-conquer approximation algorithms via spreading metrics
• The Joints Problem in $\mathbb{R}^n$
• Computing and Verifying Depth Orders
• Constructing Planar Cuttings in Theory and Practice
• Eliminating Depth Cycles among Triangles in Three Dimensions
• CUTTINGS AND APPLICATIONS
• Polynomial partitioning for a set of varieties
• On Range Searching with Semialgebraic Sets. II
• Algorithms in real algebraic geometry
• Cutting triangular cycles of lines in space
• Online point location in planar arrangements and its applications

This page was built for publication: Almost tight bounds for eliminating depth cycles in three dimensions