Balanced convex partitions of lines in the plane

2019/10/14 by Alexander Xue, Pablo Soberón, Xue, Alexander +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG

paper · pdf · doi:10.48550/arxiv.1910.06231

14 pages, 4 figures

arxiv created 2019/10/14 · arxiv updated 2019/10/15

Abstract

We prove an extension of a ham sandwich theorem for families of lines in the plane by Dujmović and Langerman. Given two sets A, B of n lines each in the plane, we prove that it is possible to partition the plane into r convex regions such that the following holds. For each region C of the partition there is a subset of c_r n^1/r lines of A whose pairwise intersections are in C, and the same holds for B. In this statement c_r only depends on r. We also prove that the dependence on n is optimal.

Related

• Happy Ending or Many Concurrent Lines
• Convex fair partitions into an arbitrary number of pieces
• Separating families of convex sets
• Balanced lines in two-coloured point sets
• A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing