## Abstract

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 R^{d} and for any positive integer D, there exists a polynomial of degree at most D whose zero set divides 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 [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 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} log^{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} 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(n^{3}/2+^{ε}) pieces that are depth-cycle free for any ε > 0. The algorithm runs in O(n^{3}/2+^{ε}) time, which is a considerable improvement over the previously known algorithms.

Original language | English (US) |
---|---|

Pages (from-to) | 1109-1127 |

Number of pages | 19 |

Journal | SIAM Journal on Computing |

Volume | 49 |

Issue number | 6 |

DOIs | |

State | Published - 2020 |

## Keywords

- Algebraic methods in combinatorial geometry
- Cycle elimination
- Depth cycle
- Depth order
- Partitioning polynomial
- ε-cutting

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics

## Fingerprint

Dive into the research topics of 'Constructive polynomial partitioning for algebraic curves in R^{3}with applications

^{∗}'. Together they form a unique fingerprint.