Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
From MaRDI portal
Publication:5138781
DOI10.1137/19M1257548zbMath1497.68515arXiv1904.09526OpenAlexW3102520527MaRDI QIDQ5138781
Joshua Zahl, Esther Ezra, Boris Aronov
Publication date: 4 December 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.09526
cycle eliminationpartitioning polynomialalgebraic methods in combinatorial geometrydepth order\( \varepsilon\)-cuttingdepth cycle
Analysis of algorithms (68W40) Real algebraic sets (14P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects of algebraic curves (14Q05) Computational real algebraic geometry (14Q30)
Related Items
On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Refined bounds on the number of connected components of sign conditions on a variety
- On the Erdős distinct distances problem in the plane
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- A deterministic view of random sampling and its use in geometry
- Efficient binary space partitions for hidden-surface removal and solid modeling
- Partitioning arrangements of lines. II: Applications
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Counting and cutting cycles of lines and rods in space
- On range searching with semialgebraic sets
- Linear size binary space partitions for uncluttered scenes
- Almost tight bounds for eliminating depth cycles in three dimensions
- Applications of random sampling in computational geometry. II
- Cutting algebraic curves into pseudo-segments and applications
- Counting and representing intersections among triangles in three dimensions
- Generalized sandwich theorems
- Binary Space Partitions for Axis-Aligned Fat Rectangles
- Optimal binary space partitions for orthogonal objects
- Eliminating Depth Cycles among Triangles in Three Dimensions
- CUTTINGS AND APPLICATIONS
- Binary Space Partitions for Fat Rectangles
- Constructive Polynomial Partitioning for Algebraic Curves in ℝ3 with Applications
- Curve-Sensitive Cuttings
- Polynomial partitioning for a set of varieties
- On Range Searching with Semialgebraic Sets. II
- Lower Bounds for Approximation by Nonlinear Manifolds
- Cutting triangular cycles of lines in space
- Algorithms in real algebraic geometry