Book contents
- Frontmatter
- Contents
- Acknowledgments
- 1 A Happy Ending
- 2 Overview
- 3 Configurations
- 4 Subconfigurations
- 5 Properties, Parameters, and Obstacles
- 6 Computing with Configurations
- 7 Complexity Theory
- 8 Collinearity
- 9 General Position
- 10 General-Position Partitions
- 11 Convexity
- 12 More on Convexity
- 13 Integer Realizations
- 14 The Stretched Geometry of Permutations
- 15 Configurations from Graphs
- 16 Universality
- 17 Stabbing
- 18 The Big Picture
- Bibliography
- Index
2 - Overview
Published online by Cambridge University Press: 04 May 2018
- Frontmatter
- Contents
- Acknowledgments
- 1 A Happy Ending
- 2 Overview
- 3 Configurations
- 4 Subconfigurations
- 5 Properties, Parameters, and Obstacles
- 6 Computing with Configurations
- 7 Complexity Theory
- 8 Collinearity
- 9 General Position
- 10 General-Position Partitions
- 11 Convexity
- 12 More on Convexity
- 13 Integer Realizations
- 14 The Stretched Geometry of Permutations
- 15 Configurations from Graphs
- 16 Universality
- 17 Stabbing
- 18 The Big Picture
- Bibliography
- Index
Summary
Many algorithmic and combinatorial problems concerning finite sets of points have been studied in discrete and computational geometry. Often, the answers to these problems depend only on knowing, for each three points, whether they are in clockwise order, counterclockwise order, or lie on a single line. It is safe, for these problems, to throw away the coordinates of the points and retain only their configuration, which tells us this ordering information for each triple of points. In many cases, in addition, the property or quantity to be studied behaves predictably under the removal of points. If removing a point can never cause a quantity of interest to increase, we call that quantity monotonic. Our goal in this work is to provide a systematic study of the monotonic properties of configurations.
Several old and colorfully named puzzles and games fit this pattern:
• The happy ending theorem was famously given its name after its proof led to the marriage of two of the mathematicians who discovered it, Esther Klein and George Szekeres. It is about how many points are needed (no three in a line) to ensure the existence of a convex polygon with a given number of corners.We described it already in Chapter 1.
• The orchard-planting problem, which we describe in Section 8.1, dates back to the early nineteenth century. It asks howmany rows of three trees one can formby planting an orchard with a given number of trees.
• We describe the no-three-in-line problem in Section 9.1. It was first posed in terms of placing 16 pawns on a chessboard, so that no three of them line up with each other. For this problem, it is important to consider all directions of lines, not just the horizontal, vertical, and diagonal directions of the chessboard.
Other topics of more serious past research also concern monotonic properties of configurations.
- Type
- Chapter
- Information
- Forbidden Configurations in Discrete Geometry , pp. 4 - 7Publisher: Cambridge University PressPrint publication year: 2018