On Sets Defining Few Ordinary Circles

• Published in: Discrete & computational geometry 2018-01, Vol.59 (1), p.59-87
• Main Authors: Lin, Aaron, Makhul, Mehdi, Mojarrad, Hossein Nassajian, Schicho, Josef, Swanepoel, Konrad, de Zeeuw, Frank
• Format: Article
• Language: English
• Subjects: Algebra; Combinatorics; Computational Mathematics and Numerical Analysis; Mathematics; Mathematics and Statistics
• ISSN: 0179-5376; 1432-0444
• DOI: 10.1007/s00454-017-9885-8

An ordinary circle of a set P of n points in the plane is defined as a circle that contains exactly three points of P . We show that if P is not contained in a line or a circle, then P spans at least n 2 / 4 - O ( n ) ordinary circles. Moreover, we determine the exact minimum number of ordinary circles for all sufficiently large n and describe all point sets that come close to this minimum. We also consider the circle variant of the orchard problem. We prove that P spans at most n 3 / 24 - O ( n 2 ) circles passing through exactly four points of P . Here we determine the exact maximum and the extremal configurations for all sufficiently large n . These results are based on the following structure theorem. If n is sufficiently large depending on K , and P is a set of n points spanning at most K n 2 ordinary circles, then all but O ( K ) points of P lie on an algebraic curve of degree at most four. Our proofs rely on a recent result of Green and Tao on ordinary lines, combined with circular inversion and some classical results regarding algebraic curves.