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
3 - Configurations
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
We begin our study with an examination of the different ways we can place small numbers of points in the plane, and what it means for two sets of points to be different.
Small Configurations
In how many different ways can we place n points in the plane? With a list of all of the possible placements, we could prove statements such as Klein's observation about convex quadrilaterals in five-point sets, automatically, merely by checking all the cases. When n is small enough, we can provide an explicit answer.
Example 3.1
There are two different ways of placing three points in the plane: they may either lie on a line, or theymay forma triangle.
Four points may be arranged in four different ways:
• a four-point line
• three points on a line and one off the line
• a triangle containing one point, or
• a convex quadrilateral.
So far, we have used only an intuitive notion for what it means for two sets of points to be the same or different. But when we get to five points, we already need to define more precisely what we mean. Figure 3.2 depicts 13 sets of five points. Are they all different from each other? Two of these are mirror images: should that count as two different sets of points or as two different views of a single way of placing five points?
We will give a more precise definition of what it means for sets of points to be the same or different in the next section. For the definition we use, mirror images are not (in general) considered to be the same, so there are indeed 13 different ways of arranging five points. Open Problem 3.5, later in this chapter, formalizes the problem of counting configurations of different sizes.
The numbers of sets of n points grow very quickly, as cn log n for a constant c > 1. Aichholzer et al. (2002) used computer searches to establish a database of small sets of points. To help control the size of the database, they exclude sets that have three points on a line and count mirror-image sets of points as equivalent. Despite these restrictions, the sets in their database still grow as cn log n, but with a smaller c.
- Type
- Chapter
- Information
- Forbidden Configurations in Discrete Geometry , pp. 8 - 18Publisher: Cambridge University PressPrint publication year: 2018