Cutting algebraic curves into pseudo-segments and applications
From MaRDI portal
Publication:2397099
Abstract: We show that a set of algebraic plane curves of constant maximum degree can be cut into Jordan arcs, so that each pair of arcs intersect at most once, i.e., they form a collection of pseudo-segments. This extends a similar (and slightly better) bound for pseudo-circles due to Marcus and Tardos. Our result is based on a technique of Ellenberg, Solymosi and Zahl that transforms arrangements of plane curves into arrangements of space curves, so that lenses (pairs of subarcs of the curves that intersect at least twice) become vertical depth cycles. We then apply a variant of a technique of Aronov and Sharir to eliminate these depth cycles by making a small number of cuts, which corresponds to a small number of cuts to the original planar arrangement of curves. After these cuts have been performed, the resulting curves form a collection of pseudo-segments. Our cutting bound leads to new incidence bounds between points and constant-degree algebraic curves. The conditions for these incidence bounds are slightly stricter than those for the current best-known bound of Pach and Sharir; for our result to hold, the curves must be algebraic and of bounded maximum degree, while Pach and Sharir's bound only imposes weaker, purely topological constraints on the curves. However, when our conditions hold, the new bounds are superior for almost all ranges of parameters. We also obtain new bounds on the complexity of a single level in an arrangement of constant-degree algebraic curves, and a new bound on the complexity of many marked faces in an arrangement of such curves.
Recommendations
- Cutting circles into pseudo-segments and improved bounds for incidences
- Lenses in arrangements of pseudo-circles and their applications
- Lenses in arrangements of pseudo-circles and their applications
- On levels in arrangements of curves, iii
- Pseudo-Line Arrangements: Duality, Algorithms, and Applications
Cites work
- A semi-algebraic version of Zarankiewicz's problem
- A Szemerédi-Trotter type theorem in R^4
- An incidence theorem in higher dimensions
- Constructing Planar Cuttings in Theory and Practice
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Cutting circles into pseudo-segments and improved bounds for incidences
- CUTTINGS AND APPLICATIONS
- How to cut pseudoparabolas into segments
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 52497 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 2209708 (Why is no real title available?)
- Intersection reverse sequences and geometric applications.
- Lenses in arrangements of pseudo-circles and their applications
- Multilevel polynomial partitions and simplified range searching
- New bounds on curve tangencies and orthogonalities
- On levels in arrangements of curves
- On levels in arrangements of curves, iii
- On levels in arrangements of curves. II: A simple inequality and its consequences
- On levels in arrangements of lines, segments, planes, and triangles
- On locally Delaunay geometric graphs
- On the Betti numbers of sign conditions
- On the complexity of arrangements of circles in the plane
- On the Erdős distinct distances problem in the plane
- On the Number of Incidences Between Points and Curves
- Polynomial partitioning for a set of varieties
- Refined bounds on the number of connected components of sign conditions on a variety
Cited in
(32)- Nöther-type theorem of piecewise algebraic curves on quasi-cross-cut partition
- How to cut pseudoparabolas into segments
- Cutting circles into pseudo-segments and improved bounds for incidences
- Triangle areas in line arrangements
- A general incidence bound in \(\mathbb{R}^d\)
- Removing depth-order cycles among triangles: an algorithm generating triangular fragments
- Corner cutting evaluation algorithms for general rational curves
- Crossings between non-homotopic edges
- Distinct distances on non-ruled surfaces and between circles
- Algebraic cuts
- Lenses in arrangements of pseudo-circles and their applications
- New bounds on curve tangencies and orthogonalities
- scientific article; zbMATH DE number 2119741 (Why is no real title available?)
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- Distinct Distances Between a Circle and a Generic Set
- Counting higher order tangencies for plane curves
- Counting and Cutting Rich Lenses in Arrangements of Circles
- An efficient algorithm for generalized polynomial partitioning and its applications
- Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
- Representation complexities of semialgebraic graphs
- Lenses in arrangements of pseudo-circles and their applications
- Semialgebraic range stabbing, ray shooting, and intersection counting in the plane
- Semi-algebraic off-line range searching and biclique partitions in the plane
- VC-dimension of hyperplanes over finite fields
- Improved estimates on the number of unit perimeter triangles
- Point-curve incidences in the complex plane
- On rich lenses in planar arrangements of circles and related problems
- On rich points and incidences with restricted sets of lines in 3-space
- Incidences with curves in \(\mathbb{R}^d\)
- Semi-algebraic off-line range searching and biclique partitions in the plane
- Incidences between curves and points on the grid
- Distinct distances with \(\ell_p\) metrics
This page was built for publication: Cutting algebraic curves into pseudo-segments and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397099)
