Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Search

Refine search

Refine search

Access:
Content type:
Publication date:
Apply   From and To filters
Subject: Show more
Journals Show more
Publishers: Show more
Societies Show more
Series: Show more
Collections: Show more

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

24 results

Page 1 of 2

  • 7 - Complexity Theory

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 43-52

  • Summary

    When we find ourselves unable to come up with an efficient algorithm for a computational problem, it is often possible to find an explanation (if not a rigorous proof that the algorithm does not exist) using the techniques of computational complexity theory.

    Decision Problems and Complexity Classes

    A computational problem can be described by a mathematical specification of its input and of the desired output for each input. This specification does not describe how to compute the output efficiently; that is the task of the algorithm designer. Within complexity theory, a special place is taken by the decision problems, the problems whose output is always either yes or no. A complexity class is a set of decision problems, usually grouped by how much time or memory their algorithms require.

    In this theory, three of the most important complexity classes are P, NP, and the class of NP-complete problems.We describe them briefly here; for an accessible and more in-depth treatment, see Fortnow (2013).

  • • P is the class of problems with yes-or-no answers that can be solved by an algorithm whose runtime is polynomial in the number of bits of input. For example, one can test whether a list of points (given by Cartesian coordinates as binary numbers) contains any repeated points, by comparing each pair of points and checking whether they are equal. This algorithm takes time proportional to the square of its input length, a polynomial. It is also possible to solve the same problemmore quickly, using sorting or hashing.

  • • NP is a larger class of yes-or-no problems, not all of which are believed to have efficient algorithms.However, whenever the answer to a problem in NP is “yes,” there must exist a short and easily checked proof that the answer is yes.Many common puzzles, such as sudoku, can be formulated as problems in NP.1 For such puzzles, the yes-or-no question is “does this puzzle have a solution?” or “if I add this step tomy answer, will it still have a solution?” The proof that it does have a solution is the solution itself. Although the solution may be hard to find, it is easy to check that it is valid.

  • 5 - Properties, Parameters, and Obstacles

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 24-32

  • Summary

    With the notions of configurations and subconfigurations in hand, we are now ready to define monotone properties andmonotone parameters.

    Definitions

    Definition 5.1

    We define a property of configurations to be something that is true of some configurations and false for others, but whose truth or falsity depends only on the configuration and not on the set of points that realizes it. A property is monotone if, whenever a configuration has the property, so do all its subconfigurations.

    We have already discussed the monotonicity of the happy ending problem.

    Example 5.2

    Containing the vertices of a convex quadrilateral is not a monotone property, but not containing a convex quadrilateral ismonotone.

    We may formalize a property either as a subset of the set of all configurations or as the characteristic function of this subset, a function of configurations that is true for the configurations with the property and false for the ones without it.

    Definition 5.3

    A parameter of configurations is a function from configurations to nonnegative integers. It is monotone if removing points from a configuration cannot cause the function value to increase.

    Example 5.4

    The size |S| of a configuration S is amonotone parameter, because all realizations of S have the same number of points, and because taking away points reduces the size.

    We can also formproperties fromparameters.

    Example 5.5

    Whenever ρ is a monotone parameter of configurations, and k is a positive integer, then the property of a configuration S of having ρ(S) < k is a monotone property of configurations. For instance, the property of having size at most four is monotone.

    Many classical problems in the discrete geometry of point sets can be formulated in terms of monotone properties and monotone parameters of configurations.

    Obstacles

    Every monotone property of configurations can be characterized by its obstacles, the smallest configurations that do not have the property.

    Definition 5.6

    If P is a monotone property of configurations, then the obstacles of P are the configurations that do not have P, but for which all proper subconfigurations do have P. P has bounded obstacles if there are finitely many obstacles for P.

  • 12 - More on Convexity

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 125-140

  • Summary

    A puzzle from the Russian mathematical olympiads asks for a proof that, for any convex pentagon of points in a grid, there is another grid point on or inside the smaller convex pentagon formed by the diagonals of the given pentagon (Figure 12.1). Thus, the grid has no empty pentagons. The existence or nonexistence of empty polygons is not a monotone property, but it suggests the study of other properties, beyond the basic ones studied in Chapter 11, based on what the convex polygons of a configuration contain and not just which points formtheir vertices.

    Weak Convexity

    A configuration S is in weakly convex position if none of the points is interior to the convex hull of S: each point either is a vertex of the convex hull (as in configurations that are in convex position) or lies on a convex hull edge. For instance, grid(2, n) is weakly convex for every n, but grid(3, 3) is not. It is tempting to guess that the weakly convex configurations are defined by the property FORBIDDEN(TETRAD), by analogy to the fact that convex = FORBIDDEN (TETRAD, LINE(3)). The three-point line is allowed in weakly convex positions, so it should be dropped fromthe list of obstacles.However, this guess is not quite right. There is one configuration that is not in weakly convex position but has no tetrad: the quincunx (Figure 12.2), a configuration formed from the four points of a convex quadrilateral together with one more point where the diagonals of the quadrilateral cross.

    The two obstacles LINE(3) and TETRAD for convex position were derived from Carathéodory's theorem, that every point in the convex hull of a set of points belongs to the convex hull of two or three points from the set. The corresponding result for weakly convex position is Steinitz's theorem that every point interior to the convex hull is interior to the convex hull of three or four points from the set. Therefore, the two forbidden patterns for weakly convex position are the tetrad and the quincunx.

  • 3 - Configurations

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 8-18

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

  • 16 - Universality

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 177-187

  • Summary

    A planar graph is a graph that can be drawn in the plane with its vertices as points and its edges as noncrossing curves (often drawn as line segments).Universal point sets are point sets that can form the vertex set of any sufficiently small planar graph. Before defining this concept more carefully as the monotone parameter universal (Definition 16.1), we look at a computer puzzle that has popularized some of these concepts.

    Planarity

    Planarity is a computer puzzle game based on planar graph drawing, originally devised by John Tantalo and Mary Radcliffe. In it, one is presented with a tangled drawing of a graph (Figure 16.1). The goal is to untangle it, by moving the vertices one by one, until the result has no crossings. As the vertices move, the edges move with them as straight line segments. Each level of the puzzle presents a more complicated graph to be untangled. Although there exist computer algorithms that can solve these puzzles efficiently, their visual complexity nonetheless makes them a challenge to human puzzle-solvers.

    The original version of this puzzle generates its graphs from arrangements of randomly generated lines (Figure 16.2, left). However, the sharp angles of these arrangements make it difficult to reconstruct them while solving the puzzle. Indeed, even finding an arrangement that generates a given graph is a hard problem, much harder than finding an untangled drawing for the graph.

    Therefore, it can be easier to search for a solution to the puzzle that places the vertices on a grid (or a rough human approximation to a grid), such as the one in Figure 16.2, right. But when we're just starting the puzzle, we don't know what the whole grid drawing will look like, if it even exists. How big should we make the grid squares? If they're too big, the drawing won't fit in the window, and we'll have to waste time and moves shrinking it. But if they're too small, it will be more difficult to precisely place each of the graph vertices into its grid position.

  • 1 - A Happy Ending

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 1-3

  • Summary

    In the early 1930s, Hungarian mathematician Esther Klein made a discovery that, despite its apparent simplicity, would kick off two major lines of research in mathematics. Klein observed that every set of five points in the plane has either three points in a line or four points in a convex quadrilateral. This became one of the first results in the two fields of discrete geometry (the study of combinatorial properties of geometric objects such as points in the Euclidean plane, and the subject of this book) and Ramsey theory (the study of the phenomenon that unstructured mathematical systems often contain highly structured subsystems).

    Klein's observation can be proven by a simple case analysis that considers how many of the points belong to their convex hull. The convex hull is a convex polygon, having some of the given points as its vertices and containing the others. It can be defined mathematically in many ways, for instance as the smallest-area convex polygon that contains all of the given points or as the largest-area simple polygon whose vertices all belong to the given points. The convex hull of points that are not all on a line always has at least three vertices (for otherwise it could not enclose a nonzero area) and, for five given points, at most five vertices. If it has five vertices, any four of them forma convex quadrilateral, and if it has four vertices then it is a convex quadrilateral. The remaining possibility for the convex hull is a triangle, with the other two points either part of a line of three points or inside the triangle.When both points are inside, and the line through themmisses the triangle vertices, it alsomisses one side of the triangle. In this case the two interior points and the two points on the missed side forma convex quadrilateral (Figure 1.1).

    The challenge of extending and generalizing this observation was taken up by two of Klein's friends, Paul Erdʺos and George Szekeres. They proved that, for every k, a convex k-gon can be found in all large enough sets of points, as long as no three of the points lie on a line. Klein later married Szekeres, and their marriage is commemorated in the name of Erdʺos and Szekeres's result: the happy ending theorem.

  • 13 - Integer Realizations

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 141-150

  • Summary

    Every general-position configuration can be realized by points with integer coordinates. However, realizing a configuration that has three or more points in a line may require the use of noninteger coordinates. The existence of an integer-coordinate realization is a monotone property, as is the existence of a realization for which all distances are integers.

    Definition 13.1

    We define the property INTEGER-COORDINATES(S) to be true when S can be realized by points all of whose Cartesian coordinates are integers. We define the property INTEGER-COORDINATES(S) to be true when S can be realized by points all of whose pairwise Euclidean distances are integers.

    Another way of defining integer-coordinates(S) is that it is the property of being a subconfiguration of grid(n) for some n. On the other hand, it is not known whether all grids can be realized with integer distances. Figure 13.1 shows an integer-distance realization of grid(2, 3).

    Open Problem 13.2

    Which grids can be realized with integer distances?

    We could equivalently substitute the rational numbers for the integers. Any set of points whose coordinates or distances are rational can be scaled tomake them integers, without changing its order type. Klee and Wagon (1991) trace the history of the integer distance problem (in its equivalent formulation with rational numbers) to the seventh-century Indianmathematician Brahmagupta, who already asked about rational-distance realizations of POLYGON(4).

    The Perles Configuration

    The realizability of configurations using rational coordinates was considered by Micha Perles in the 1960s. Perles found an unrealizable configuration now called the Perles configuration, consisting of nine points at the corners and center of a regular pentagram (Figure 13.2).

    The properties of this configuration depend on the projective transformations of the plane and on a number defined fromquadruples of collinear points called their cross-ratio. A projective transformation is a transformation of the plane that preserves collinearities among all of the (infinitely many) triples of points in the plane. The cross-ratio of four distinct points A, B, C, and D appearing in that order along a line is defined as

  • 15 - Configurations from Graphs

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 166-176

  • Summary

    Many results on the hardness of subconfiguration-related problems can be based on graph drawing algorithms that create configurations fromthe vertices and edges of a graph. The value of a monotone parameter of configurations, on a configuration generated from a graph, can often provide useful information about the graph that the configuration came from. If this information would allow us to solve a graph problem that is known to be hard, then computing the parametermust be hard as well.

    Definitions

    In this sectionwe briefly summarize the terminology fromgraph theory thatwe need here.

    Definition 15.1 (graphs, vertices, and edges)

    A graph, for our purposes, consists of a pair (V, E) where V is a finite set and E is a set of unordered pairs of elements of V. The elements of V are called vertices (a single one is a vertex) and the elements of E are called edges.1 The two vertices of each edge are called its endpoints. A vertex and edge are incident if the vertex is an endpoint of the edge. Two vertices are adjacent if they are both the endpoints of the same edge.

    Definition 15.2 (graph drawings and planar graphs)

    A drawing of a graph is a representation of the vertices by points in the plane and the edges by curves from one endpoint to the other that avoid the other vertices. A crossing in a drawing is a point where two edges intersect, other than at a shared endpoint of the edges. A drawing is planar if it has no crossings, and a graph is a planar graph if it can be drawn without crossings. Although, as mathematical objects, the vertices of a drawing are points, we will represent them in figures by small disks, as we do for other kinds of points (Figure 15.1).11

    Definition 15.3 (paths and connectivity)

    A path in a graph is an alternating sequence of vertices and edges, starting and ending with vertices, and with each consecutive pair of a vertex and an edge incident to each other. A graph is connected if every two vertices can be the first and last vertex of at least one path. An isolated vertex is a vertex that has no incident edges.

  • 18 - The Big Picture

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 207-210

  • Summary

    As we have seen, many long-known problems from discrete geometry can be brought into the picture of monotone properties and parameters of configurations. Along the way, we have found obstacles and algorithms for many of these parameters.We have also shown thatmany pairs of these parameters are either equivalent for the purposes of fixed-parameter tractability (when each is bounded by a function of the other) or related by bounds in only one direction. Figure 18.1 shows some of these parameters and their relations.

    In the next two sections, we summarize the key results about these properties and parameters.

    Properties

    COLLINEAR is the property of having all points on a single line (Definition 8.2). It may be tested in linear time (Section 8.4). There is only one collinear configuration of each size n, the configuration line(n). It has one obstacle, polygon(3).

    CONVEX is the property of forming the vertices of a convex polygon (Definition 11.1). It may be tested in polynomial time by computing the convex hull (Section 11.4). There is only one convex configuration of each size n, the configuration polygon(n). It has a finite set of obstacles.

    GENERAL-POSITION is the property of being in general position, true of point sets with no three in a line (Definition 9.1). Thus, it has one obstacle, line(3). It may be tested in quadratic time (Section 9.2).

    INTEGER-COORDINATES(S) is the property of being realizable with integer coordinates, true of subconfigurations of grids (Definition 13.1). It includes all configurations in general position and all weakly convex configurations. We do not know its obstacles or computational complexity (Open Problem 13.4).

    INTEGER-DISTANCES(S) is the property of being realizable with all pairwise distances equal to integers (Definition 13.1). It includes all configurations in convex position (Section 13.2). We do not know its obstacles or computational complexity (Open Problem 13.4).

    STRETCHED is a property that characterizes the configurations generated by the stretching transformation (Definition 14.5), used to represent permutations by point sets (Observation 14.7). It may be tested in polynomial time (Theorem 14.23). Finding subconfigurations of stretched configurations is fixedparameter tractable (Theorem 14.26).

    WEAKLY-CONVEX is the property of being in weakly convex position (Definition 12.1). It has a finite set of obstacles andmay be computed in polynomial time (Section 12.2). The weakly convex configurations are not well-quasiordered (Theorem 12.3).

  • 4 - Subconfigurations

  • David Eppstein, University of California, Irvine
  • Book:
    Forbidden Configurations in Discrete Geometry
    Published online:
    04 May 2018
    Print publication:
    17 May 2018, pp 19-23

  • Summary

    How many sides can a convex polygon with vertices in a 5 × 5 grid have? To avoid spoiling this puzzle we defer the answer to Figure 11.3. Just as one set of points may be a subset of another, one configuration may be a subconfiguration of another. The puzzle seeks a polygon subconfiguration of grid(5, 5). We define subconfigurations more carefully in the rest of this chapter. In Chapter 5, we will use them to define monotone properties and parameters and to find obstacles, the subconfigurations that prevent a given configuration from having a property.

    Definitions

    Definition 4.1

    A subconfiguration of a configuration S is any configuration that can be obtained from a realization of S by removing zero or more points. If T is a subconfiguration of S, an instance of T in S is a one-to-one matching of points in T to a subset of points in S so the matched points have the same orientations in T and in S. Each configuration is a subconfiguration of itself; T is a proper subconfiguration of S if it is a subconfiguration but unequal to S.

    Example 4.2

    Figure 4.1 shows all of the configurations on one to four points, with lines indicating pairs of subconfigurations that differ from each other by the addition or removal of a single point. In this diagram, one configuration is a subconfiguration of another if the two configurations are connected by a monotone path. For instance, the one-point configuration at the bottom of the diagram is a subconfiguration of all of the other configurations.

    Note that the subconfigurations of a configuration T are not subsets of T, because T is not a set of points (it is an equivalence class of sets of points).

    Partial Orders and Quasi-Orders

    The subconfiguration relation between configurations forms an example of a partial order. This means that, if we write S→ T when S is a subconfiguration of T, then this relation →obeys the following three axioms:

  • • Reflexivity: For all configurations X, X → X.

  • • Anti-symmetry: For all configurations X and Y, if X _→Y and Y → X, then X = Y.

  • • Transitivity: For all configurations X, Y, and Z, if X →Y and Y → Z, then X → Z.

Page 1 of 2