Constructive polynomial partitioning for algebraic curves in R^3 with applications

DOI10.1137/19M1257548zbMATH Open1497.68515arXiv1904.09526OpenAlexW3102520527MaRDI QIDQ5138781FDOQ5138781

Authors: Esther Ezra, J. Zahl, Boris Aronov 

Publication date: 4 December 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: In 2015, Guth proved that for any set of $k$-dimensional bounded complexity varieties in $mathbb{R}^d$ and for any positive integer $D$, there exists a polynomial of degree at most $D$ whose zero set divides $mathbb{R}^d$ into open connected sets, so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for $k>0$, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in $mathbb{R}^3$. We present an efficient algorithmic construction for this setting. Given a set of $n$ input algebraic curves and a positive integer $D$, we efficiently construct a decomposition of space into $O(D^{3}lo{g}^{3}D)$ open "cells," each of which meets $O(n/D^2)$ curves from the input. The construction time is $O(n^2)$. For the case of lines in $3$-space we present an improved implementation, whose running time is $O(n^{4/3}lo{g}^{O(1)}n)$. The constant of proportionality in both time bounds depends on $D$ and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among non-vertical lines in $3$-space, recently studied by Aronov and Sharir (2018), and show an algorithm that cuts $n$ such lines into $O(n^{3/2+epsilon})$ pieces that are depth-cycle free, for any $epsilon>0$. The algorithm runs in $O(n^{3/2+epsilon})$ time, which is a considerable improvement over the previously known algorithms.

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

Recommendations

• Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
• Almost tight bounds for eliminating depth cycles in three dimensions
• Almost tight bounds for eliminating depth cycles in three dimensions
• Multilevel polynomial partitions and simplified range searching
• On range searching with semialgebraic sets. II.

zbMATH Keywords

cycle eliminationpartitioning polynomialalgebraic methods in combinatorial geometrydepth order\( \varepsilon\)-cuttingdepth cycle

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Real algebraic sets (14P05) Computational aspects of algebraic curves (14Q05) Computational real algebraic geometry (14Q30)

Cites Work

• Applications of random sampling in computational geometry. II
• Title not available (Why is that?)
• On the Erdős distinct distances problem in the plane
• Computational geometry. Algorithms and applications.
• Algorithms in real algebraic geometry
• A deterministic view of random sampling and its use in geometry
• CUTTINGS AND APPLICATIONS
• On Range Searching with Semialgebraic Sets. II
• Lower Bounds for Approximation by Nonlinear Manifolds
• Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
• Title not available (Why is that?)
• Generalized sandwich theorems
• Refined bounds on the number of connected components of sign conditions on a variety
• On range searching with semialgebraic sets
• Linear size binary space partitions for uncluttered scenes
• Counting and representing intersections among triangles in three dimensions
• Counting and cutting cycles of lines and rods in space
• Binary Space Partitions for Axis-Aligned Fat Rectangles
• Optimal binary space partitions for orthogonal objects
• Binary Space Partitions for Fat Rectangles
• Efficient binary space partitions for hidden-surface removal and solid modeling
• Title not available (Why is that?)
• Polynomial partitioning for a set of varieties
• Partitioning arrangements of lines. II: Applications
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Cutting algebraic curves into pseudo-segments and applications
• Curve-Sensitive Cuttings
• Almost tight bounds for eliminating depth cycles in three dimensions
• Title not available (Why is that?)
• Eliminating Depth Cycles among Triangles in Three Dimensions
• Cutting triangular cycles of lines in space
• Constructive Polynomial Partitioning for Algebraic Curves in ℝ³ with Applications

Cited In (2)

• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• On Ray Shooting for Triangles in 3-Space and Related Problems

This page was built for publication: Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138781)