TY - JOUR

T1 - Constructive polynomial partitioning for algebraic curves in R3 with applications∗

AU - Aronov, Boris

AU - Ezra, Esther

AU - Zahl, Joshua

N1 - Funding Information:
∗Received by the editors April 22, 2019; accepted for publication (in revised form) July 23, 2020; published electronically November 12, 2020. A preliminary version of this work was presented in Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019 [8]. https://doi.org/10.1137/19M1257548 Funding: The first author has been supported by NSF grants CCF-11-17336, CCF-12-18791, and CCF-15-40656 and by BSF grant 2014/170. The second author has been supported by NSF CAREER under grant CCF:AF 1553354 and by grant 824/17 from the Israel Science Foundation. The third author was supported by a NSERC Discovery grant. †Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY 11201 USA (boris.aronov@nyu.edu). ‡Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel (ezraest@cs.biu.ac.il). §Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada (jzahl@math.ubc.ca).
Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics

PY - 2020

Y1 - 2020

N2 - In 2015, Guth [Math. Proc. Cambridge Philos. Soc., 159 (2015), pp. 459-469] proved that for any set of k-dimensional bounded complexity varieties in Rd and for any positive integer D, there exists a polynomial of degree at most D whose zero set divides Rd 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 [Ann. Math., 181 (2015), pp. 155-190] 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 R3. 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(D3 log3 D) open “cells,” each of which meets O(n/D2) curves from the input. The construction time is O(n2). For the case of lines in 3-space, we present an improved implementation whose running time is O(n4/3 polylog 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 nonvertical lines in 3-space, recently studied by Aronov and Sharir [Discrete Comput. Geom., 59 (2018), pp. 725-741] and show an algorithm that cuts n such lines into O(n3/2+ε) pieces that are depth-cycle free for any ε > 0. The algorithm runs in O(n3/2+ε) time, which is a considerable improvement over the previously known algorithms.

AB - In 2015, Guth [Math. Proc. Cambridge Philos. Soc., 159 (2015), pp. 459-469] proved that for any set of k-dimensional bounded complexity varieties in Rd and for any positive integer D, there exists a polynomial of degree at most D whose zero set divides Rd 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 [Ann. Math., 181 (2015), pp. 155-190] 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 R3. 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(D3 log3 D) open “cells,” each of which meets O(n/D2) curves from the input. The construction time is O(n2). For the case of lines in 3-space, we present an improved implementation whose running time is O(n4/3 polylog 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 nonvertical lines in 3-space, recently studied by Aronov and Sharir [Discrete Comput. Geom., 59 (2018), pp. 725-741] and show an algorithm that cuts n such lines into O(n3/2+ε) pieces that are depth-cycle free for any ε > 0. The algorithm runs in O(n3/2+ε) time, which is a considerable improvement over the previously known algorithms.

KW - Algebraic methods in combinatorial geometry

KW - Cycle elimination

KW - Depth cycle

KW - Depth order

KW - Partitioning polynomial

KW - ε-cutting

UR - http://www.scopus.com/inward/record.url?scp=85097238966&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097238966&partnerID=8YFLogxK

U2 - 10.1137/19M1257548

DO - 10.1137/19M1257548

M3 - Article

AN - SCOPUS:85097238966

SN - 0097-5397

VL - 49

SP - 1109

EP - 1127

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -