# Forbidden Configurations in Discrete Geometry

## David Eppstein

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.

## Reviews:

• Darren Glass, MAA Reviews, July 2018: “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, March 2019: “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.”

• 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.

• 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.

• 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. 2018. A note on universal point sets for planar graphs. Electronic preprint https://arxiv.org/abs/1811.06482.

• 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.

• In section 18.2, “size” is inappropriately bold.

• 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.