On Equal Point Separation by Planar Cell Decompositions

2017/01/17 by Nikhil Marda, Marda, Nikhil
Computer Science · Mathematics · #05D10 #52A10 #53A04 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05D10 #msc:52A10 #msc:53A04

paper · pdf · doi:10.48550/arxiv.1701.04529

19 pages, 9 figures

arxiv created 2017/01/17 · openalex publication_date 2017/01/17 · arxiv updated 2017/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we investigate the problem of separating a set X of points in ℝ² with an arrangement of K lines such that each cell contains an asymptotically equal number of points (up to a constant ratio). We consider a property of curves called the stabbing number, defined to be the maximum countable number of intersections possible between the curve and a line in the plane. We show that large subsets of X lying on Jordan curves of low stabbing number are an obstacle to equal separation. We further discuss Jordan curves of minimal stabbing number containing X. Our results generalize recent bounds on the Erdős-Szekeres Conjecture, showing that for fixed d and sufficiently large n, if |X| ≥ 2^{c_dn/d + o(n)} with c_d = 1 + O((1)/(√(d))), then there exists a subset of n points lying on a Jordan curve with stabbing number at most d.

Related

• On Separating Points by Lines
• Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique
• On the Erdos distinct distance problem in the plane
• On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves
• On the number of touching pairs in a set of planar curves