Published in 2018 by Cambridge University Press, this book surveys many famous problems in the geometry of finite point sets in the plane, unifying them under the framework of properties that depend only on how triples of points are oriented and that behave monotonically as points are removed, and covering both mathematical and computational aspects of the subject. It is aimed at a range of readers from advanced undergraduates in mathematics and computer science to research professionals.
Darren Glass, MAA Reviews: “There is a lot to like about this book, as Eppstein does a good job of introducing the material to his readers. I will note that I think many mathematicians will find certain aspects of Eppstein’s writing style and notational conventions to be different from what we are used to, and while I found his choice of topics interesting I know that the book made me think of many more questions that he did not address. A reader who sticks with Eppstein will learn a lot about this exciting area that lies on the border of mathematics and computer science.”
László Szabó, Mathematical Reviews: “The book is a great read. It is a valuable addition to the library of any discrete or computational geometer. Moreover, it can also serve as an excellent textbook for an introductory course on point configurations.”
Andrea Švob, zbMATH: “This very interesting study has strong connections with problems concerning graph theory, theory of permutation and number theory and as such has many applications in various fields.”
D. V. Feldman, Choice: “The first systematic exposition of the present topic … Eppstein deftly sells the subject to the uninitiated, yet carries it to depths experts will appreciate. … Highly recommended.”
Daniel Kleitman, Inference: “The nature of the questions Eppstein examines are easily understandable for non-mathematicians, and the treatment is, for the most part, accessible to well-informed readers. The book will be of great interest for budding mathematicians, in particular, who will find plenty of stimulating questions to consider, many of which are not usually encountered as part of a mathematics curriculum.”
Frederic Green, SIGACT News: “While the geometry studied in the book pretty much confines itself to two dimensions, the mathematical ideas synthesized here are multi-dimensional: Geometry, algorithms, complexity, parameterized complexity, property testing, and combinatorics all play key roles (and this is only a partial list). It is very enlightening to see some of these less “geometrical” topics (such as complexity) manifest themselves in pictorial ways.”
Open Problem 3.14 (the maximum number of halving partitions) should have been credited to the paper that introduced this problem:
Erdős, Paul, Lovász, László; Simmons, A., and Straus, Ernst G. 1973. Dissection graphs of planar point sets. Pages 139–149 of: A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). Amsterdam: North-Holland.
Section 6.5 (property testing) should have credited the following paper, where the model of property testing used here originates:
Czumaj, Artur, Sohler, Christian, and Ziegler, Martin. 2000. Property testing in computational geometry. Pages 155–166 of: 8th European Symposium on Algorithms (ESA 2000). Lecture Notes in Computer Science, vol. 1879, Berlin: Springer.
Theorem 7.3 states that, under the exponential time hypothesis, no algorithm with running time \(n^{o(\sqrt{k})}\) can test whether a configuration of size \(k\) is a subconfiguration of an input of size \(n\). The proof uses convex embedding to reduce from finding cliques in graphs. The conclusion can be strengthened to running time \(n^{o(k/\log k)}\) using a similar reduction from labeled subgraph isomorphism (this problem is described e.g. in Eppstein and Lokshtanov 2018).
Open problem 7.6 (the existence of a finite set of obstacles such that finding a \(k\)-point set avoiding the obstacles is not fixed-parameter tractable) has been solved by the following paper:
Eppstein, David, and Lokshtanov, Daniel. 2018. The parameterized complexity of finding point sets with hereditary properties. Pages 11:1–11:14 of: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics, vol. 115, Dagstuhl: Leibniz-Zentrum für Informatik.
It shows that under standard complexity-theoretic assumptions there is no FPT algorithm for this general problem: for the three obstacles below, this problem is \(\mathsf{W}[1]\)-hard, and no algorithm can solve the problem in time \(n^{o(k/\log k)}\) unless the exponential time hypothesis fails.
Theorem 9.3 states in part that finding the largest general-position subset is \(\mathsf{NP}\)-hard and \(\mathsf{APX}\)-hard, and Theorem 9.5 states that it is fixed-parameter tractable in the size of the subset. The same results are proven in:
Froese, Vincent, Kanj, Iyad, Nichterlein, André, and Niedermeier, Rolf. 2017. Finding points in general position. Int. J. Comput. Geom. Appl. 27(4), 277–296.
Theorem 9.13 of Payne and Wood implies that every \(n\)-point set has a subset of size \(\Omega(\sqrt{n/\log n})\) that is either collinear or in general position. A new result of Hajnal and Szemerédi improves this to \(\Omega(\sqrt{n\log\log n/\log n})\):
Hajnal, Péter, and Szemerédi, Endre. 2018. Two geometrical applications of the semi-random method. Pages 188–199 of: New Trends in Intuitive Geometry. Bolyai Society Mathematical Studies, vol. 27, Berlin: Springer.
The proof of Theorem 9.16 is missing a factor of \(\sqrt2\) in two of its formulas.
Theorem 10.12 on point sets with no four in line and no general-position subset larger than \(O(n^{5/6+\epsilon})\) is credited to a 2017 preprint by Balogh and Solymosi. Their paper has now been published. It is:
Balogh, Jozsef, and Solymosi, Jozsef. 2018. On the number of points in general position in the plane. Discrete Analysis 2018(16), 20pp.
Observation 11.7 gives asymptotic bounds on the largest convex polygon in a grid, and figure 11.3 gives an example of the largest polygon in a \(5\times 5\) grid. More precise asymptotic bounds for the square grid were given by
Acketa, Dragan M. and Žunić, Joviša D. 1995. On the maximal number of edges of convex digital polygons included into an \(m\times m\)-grid. J. Combin. Theory Ser. A 69(2), 358–368.
Exact values were determined by
Kisman, Derek, Guy, Richard, and Fink, Alex. 2009. Patulous pegboard polygons. Pages 59–68 of: Mathematical Wizardry for a Gardner. Wellesley, MA: A K Peters.
The following paper considers similar problems for other shapes than squares:
Bárány, Imre and Prodromou, Maria. 2006. On maximal convex lattice polygons inscribed in a plane convex set. Israel J. Math. 154, 337–360.
See also my blog post “big convex polygons in grids” for more on this topic.
Open problem 11.10 (the sample size for property testing convex position) was already answered by Czumaj, Sohler, and Ziegler (2000). The optimal sample size is \(\Theta(n^{2/3})\).
One proof of this (not the one they give) is to consider any point \(p\) of high Tukey depth, observe that logarithmically many samples are enough to have high probability of enclosing \(p\), and consider the nonconvex quadruples of points formed by \(p\) and three given points. If linearly many quadruples are disjoint (except for \(p\)) then one is likely to be found by the remaining sample points; otherwise, deleting all of the points in a maximal disjoint family of quadruples shows that the input is near-convex.
Pages 144–145, of section 13.2, describe a construction credited to Harborth, claimed to produce a dense set of points with rational distances on a unit circle, consisting of all points on the circle that are integer multiples of the angle of an integer right triangle. It is possible to produce a set with these properties with almost the same construction, but Harborth stated the construction incorrectly. One needs to use only the even multiples of this angle rather than all integer multiples. For details, see my blog post “correcting Harborth on rational distances”.
Footnotes 6 and 7 of section 13.4 give two references for sets of seven points in the plane, all at integer distances, with no three on a line and no four on a circle. Many more such sets with the additional property that all coordinates are integers (including the set with the smallest possible diameter) were found by:
Kurz, Sascha, Noll, Landon Curt, Rathbun, Randall, and Simmons, Chuck. 2014. Constructing 7-clusters. Serdica J. Comput. 8(1), 47–70.
Their paper provides several additional references to earlier work on this problem.
Footnote 4 at the start of Section 16.3 lists three papers on linear lower bounds for universal point sets. A new fourth paper improves them, but the bound is still linear:
Scheucher, Manfred, Schrezenmaier, Hendrik, and Steiner, Raphael. 2019. A note on universal point sets for planar graphs. 27th International Symposium on Graph Drawing and Network Visualization.
The proof of Theorem 16.13 (universal point sets cannot be covered by few lines) used the fact that certain graphs, the Apollonian networks, cannot be drawn with their points on a bounded number of lines. This was already known for a different class of planar graphs, the maximal planar graphs of small dual shortness exponent. See the following two papers:
Ravsky, Alexander, and Verbitsky, Oleg. 2011. On collinear sets in straight-line drawings. Pages 295–306 of: 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011). Lecture Notes in Computer Science, vol. 6986, Berlin: Springer.
Chaplick, Steven, Fleszar, Krzysztof, Lipp, Fabian, Verbitsky, Oleg, and Wolff, Alexander. 2016. Drawing graphs on few lines and few planes. Pages 166–180 of: 24th International Symposium on Graph Drawing and Network Visualization. Lecture Notes in Computer Science, vol. 9801, Berlin: Springer.
For recent developments on drawing planar graphs on few lines, see:
Eppstein, David. 2019. Cubic planar graphs that cannot be drawn on few lines. Pages 32:1–32:15 of: 35th International Symposium on Computational Geometry. Leibniz International Proceedings in Informatics (LIPIcs), vol. 129. Dagstuhl, Germany: Leibniz-Zentrum für Informatik.
Felsner, Stefan. 2019. 4-connected triangulations on few lines. 27th International Symposium on Graph Drawing and Network Visualization.
Biedl, Therese, Felsner, Stefan, Meijer, Henk, and Wolff, Alexander. 2019. Line and plane cover numbers revisited. 27th International Symposium on Graph Drawing and Network Visualization.
Open Problem 17.5 has been solved by Johannes Obenaus, a master’s student at the Free University of Berlin and ETH Zurich. There exist sets of points with the property that removing points from the set causes the minimum stabbing number of a spanning tree of the points to increase, so TREE-STAB is not monotone. See:
Obenaus, Johannes. 2019. Spanning Trees with Low (Shallow) Stabbing Number. Master’s Thesis, Free University of Berlin (joint with ETH Zurich).
In section 18.2, “size” is inappropriately bold.
There is a typo in the title of the Euler reference. Instead of “depromta” it should be “deprompta”. The reference can be found online in the Euler archive.
In the references and index, the paper “Point sets with many \(k\)-sets” (Discrete Comput. Geom. 2001) is credited to Gabor Tóth. The correct author of the paper is Geza Tóth.
