On Sets of n Points in General Position That Determine Lines That Can Be Pierced by n Points
- PDF / 378,461 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 27 Downloads / 159 Views
On Sets of n Points in General Position That Determine Lines That Can Be Pierced by n Points Chaya Keller1 · Rom Pinchasi1 Received: 20 August 2019 / Revised: 14 January 2020 / Accepted: 26 February 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let P be a set of n points in general position in the plane. Let R be a set of n points disjoint from P such that for every x, y ∈ P the line through x and y contains a point in R outside of the segment delimited by x and y. We show that P ∪ R must be contained in cubic curve. This resolves a special case of a conjecture of Mili´cevi´c. We use the same approach to solve a special case of a problem of Karasev related to a bipartite version of the above problem. Keywords Elliptic curves · Cubic curves · Points · Lines · Line blocker
1 Introduction A beautiful result of Motzkin [13], Rabin, and Chakerian [4] states that any set of noncollinear red and blue points in the plane determines a monochromatic line. Grünbaum and Motzkin [8] initiated the study of biased coloring, that is, coloring of the points such that no purely blue line is determined. The intuition behind this study is that if the number of blue points is much larger than the number of red points, then unless the set of blue points is collinear, the set of blue and red points should determine a
Dedicated to the memory of Ricky Pollack Editor in Charge: János Pach Chaya Keller and Rom Pinchasi: Research partially supported by Grant 409/16 from the Israel Science Foundation. Chaya Keller [email protected] Rom Pinchasi [email protected] 1
Mathematics Department, Technion – Israel Institute of Technology, 32000 Haifa, Israel
123
Discrete & Computational Geometry
Fig. 1 Constructions with |R| = n − 1 for n = 2, 4. The points in P are colored black while the points in R are colored white
monochromatic blue line. The same problem was independently considered by Erd˝os and Purdy [6] who stated it in a slightly different way. Let P be a set of n points in the plane. Erd˝os and Purdy asked the following question in [6]: Assume a set R of points in the plane is disjoint from P and has the property that every line determined by P passes through a point in R. How small can be the cardinality of R in terms of n? Clearly, if P is contained in a line, then R may consist of just one point. Therefore, the question of Erd˝os and Purdy is about sets P that are not collinear. The best known lower bound for this question is given in [16], where it is shown that |R| ≥ n/3. In [6] Erd˝os and Purdy considered the same problem in the case where the set P is in general position in the sense that no three points of P are collinear. In this case if n is odd the tight bound |R| ≥ n is almost trivial because every point in R may be incident to at most (n − 1)/2 of the n2 lines determined by P. To observe that this bound is tight let P be the set of vertices of a regular n-gon and let R be the set of n points on the line at infinity that correspond to the directions of the edges (and diag
Data Loading...
