Constructive Polynomial Partitioning for Algebraic Curves in\n $\\mathbb{R}^3$ with Applications

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

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.