# 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.”

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

• 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, Dagstuhl: Leibniz-Zentrum für Informatik, to appear.

In it, the authors show that under standard complexity-theoretic assumptions there is no FPT algorithm for this general problem. They provide a set of three obstacles for which this problem is $\mathsf{W}[1]$-hard, and for which 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.

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

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