2019/01/01 by Boris Aronov, Aronov, Boris, Esther Ezra +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1904.09526
openalex publication_date 2019/01/01 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
In 2015, Guth proved that for any set of k-dimensional bounded complexity\nvarieties in \ℝd and for any positive integer D, there exists a\npolynomial of degree at most D whose zero set divides \ℝ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 \ℝ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(D3\log3D) open "cells," each of\nwhich meets O(n/D2) curves from the input. The construction time is\nO(n2). For the case of lines in 3-space we present an improved\nimplementation, whose running time is O(n4/3 \logO(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(n3/2+\ε)\npieces that are depth-cycle free, for any \ε > 0. The algorithm runs in\nO(n3/2+\ε) time, which is a considerable improvement over the\npreviously known algorithms.\n