Balanced Convex Partitions of Lines in the Plane
- PDF / 446,090 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 118 Downloads / 193 Views
Balanced Convex Partitions of Lines in the Plane Alexander Xue1 · Pablo Soberón2 Received: 26 October 2019 / Revised: 26 August 2020 / Accepted: 9 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We prove an extension of a ham sandwich theorem for families of lines in the plane by Dujmovi´c 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 closed convex regions so that the following holds. For each region C of the partition there is a subset of cr n 1/r lines of A whose pairwise intersections are in C, and the same holds for B. In this statement cr only depends on r . We also prove that the dependence on n is optimal. For a single set A of n lines, we prove that there exists a partition of the plane into r parts using r − 1 vertical lines such that each region contains the pairwise intersections of a set of n 1/r lines of A. The value n 1/r is optimal. Keywords Convex partition · Families of lines · Mass partition Mathematics Subject Classification 52C30 · 52A99 · 54H25
1 Introduction A general measure partition problem deals with the way we can split points or measures in Euclidean spaces. Given a set of rules to split the ambient space, we are interested to know if we can divide a given set of points in a prescribed way. The quintessential result of this kind is the classic ham sandwich theorem.
Editor in Charge: János Pach This research project was done as part of the 2019 CUNY Combinatorics REU, supported by NSF awards DMS-1802059 and DMS-1851420. Alexander Xue [email protected] Pablo Soberón [email protected] 1
Cornell University, Ithaca, NY 14850, USA
2
Baruch College, City University of New York, One Bernard Baruch Way, New York, NY 10010, USA
123
Discrete & Computational Geometry
Theorem We are given d sets of points in Rd in general position. If each set has an even cardinality, there exists a hyperplane that simultaneously splits each set exactly by half. The proof of a mass partition result usually boils down to understanding topological properties of the space of partitions [20]. The methods developed to tackle measure partitions problems have broad applications in combinatorial topology. In this manuscript we are interested in extensions of the ham sandwich theorem for convex partitions of the plane. A convex partition of R2 into r parts is a family of closed sets C1 , . . . , Cr ⊂ R2 such that • the sets cover R2 , so ri=1 Ci = R2 , • the interiors of the sets are pairwise disjoint, and • each Ci is a closed convex set. The ham sandwich theorem has been generalized to convex partitions of the plane. The following theorem was proven independently by Ito et al. [13], by Bespamyatnikh et al. [2], and by Sakai [16]. Theorem 1.1 Let A1 , A2 be two sets of points in R2 , in general position. If the cardinality of each set is a multiple of r , there exists a closed convex partition of the plane into r sets C1 , . . . , Cr such that for each i ∈ {1, 2}, j ∈ {1, 2, .
Data Loading...
