Heilbronn triangle problem
In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points. His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown. Definition. The Heilbronn triangle problem concerns the placement of formula_1 points within a shape in the plane, such as  the unit square or the unit disk, for a given Each triple of points form the three vertices of a triangle, and among these triangles, the problem concerns the smallest triangle, as measured by area. Different placements of points will have different smallest triangles, and the problem asks: how should formula_1 points be placed to maximize the area of the smallest More formally, the shape may be assumed to be a compact set formula_3 in the plane, meaning that it stays within a bounded distance from the origin and that points are allowed to be placed on its boundary. In  most work on this problem, formula_3 is additionally a convex set of nonzero area. When three of the placed points lie on a line, they are considered as forming a degenerate triangle whose area is defined to be zero, so placements that maximize the smallest triangle will not have collinear triples of points. The assumption that the shape is compact implies that there exists an optimal placement of formula_1 points, rather than only a sequence of placements approaching optimality. The number formula_6 may be defined as the area of the smallest triangle in this optimal An example is shown in  the figure, with six points in a unit square. These six points form formula_7 different triangles, four of which are shaded in the figure. Six of these 20 triangles, with two of the shaded shapes, have area 1/8; the remaining 14 triangles have larger areas. This is the optimal placement of six points in a unit square: all other placements form a triangle with area 1/8 or smaller. Therefore, Although researchers have studied the value of formula_6 for specific shapes and specific small numbers of points, Heilbronn was concerned instead about its asymptotic behavior: if the shape formula_3 is held  fixed, but formula_1 varies, how does the area of the smallest triangle vary That is, Heilbronn's question concerns the growth rate as a function For any two shapes formula_3 the numbers formula_6 and formula_13 differ only by a constant factor, as any placement of formula_1 points within formula_3 can be scaled by an affine transformation to fit changing the minimum triangle area only by a constant. Therefore, in bounds on the growth rate of formula_6 that omit the constant of proportionality of that growth, the choice of formula_3 is irrelevant and the subscript may be Heilbronn's conjecture and  its disproof. Heilbronn conjectured prior to 1951 that the minimum triangle area always shrinks rapidly as a function —more specifically, inversely proportional to the square In terms of big O notation, this can be expressed as the bound formula_18 In the other direction, Paul Erdős found examples of point sets with minimum triangle area proportional demonstrating that, if true, Heilbronn's conjectured bound could not be strengthened. Erdős formulated the no-three-in-line problem, on large sets of grid points with no three in a line, to describe these examples. As Erdős observed, when formula_1 is a prime number , the set of formula_1 points formula_21 on an formula_22 integer grid (for have no three collinear points, and therefore by Pick's formula each of the triangles they form has area at When these grid points are scaled to fit within a unit square, their smallest triangle area is proportional matching Heilbronn's conjectured upper bound. If formula_1 is not prime, then a similar construction using a prime number close to formula_1 achieves the same asymptotic lower The area resulting from their construction grows asymptotically as formula_27 The proof can be derandomized, leading to a polynomial-time algorithm for constructing  placements with this triangle area. Upper bounds. Every set of formula_1 points in the unit square forms a triangle of area at most inversely proportional One way to see this is to triangulate the convex hull of the given point and choose the smallest of the triangles in the triangulation. Another is to sort the points by their and to choose the three consecutive points in this ordering whose are the closest together. In the first paper published on the Heilbronn triangle problem, in 1951, Klaus Roth proved a stronger upper bound of the form formula_29 The best bound known  to date is of the form formula_30 for some proven by . Specific shapes and numbers. has investigated the optimal arrangements of formula_1 points in a square, for formula_1 up to 16. Goldberg's constructions for up to six points lie on the boundary of the square, and are placed to form an affine transformation of the vertices of a regular polygon. For larger values improved Goldberg's bounds, and for these values the solutions include points interior to the square. These constructions have been proven optimal for up to seven points. The proof used a computer search to subdivide the  configuration space of possible arrangements of the points into 226 different subproblems, and used nonlinear programming techniques to show that in 225 of those cases, the best arrangement was not as good as the known bound. In the remaining case, including the eventual optimal solution, its optimality was proven using symbolic computation techniques. Instead of looking for optimal placements for a given shape, one may look for an optimal shape for a given number of points. Among convex shapes formula_3 with area one, the regular hexagon is the one that for this shape, with six points optimally placed at the  hexagon vertices. The convex shapes of unit area that maximize formula_34 have Variations. There have been many variations of this problem including the case of a uniformly random set of points, for which arguments based on either Kolmogorov complexity or Poisson approximation show that the expected value of the minimum area is inversely proportional to the cube of the number of points. Variations involving the volume of higher-dimensional simplices have also been studied. Rather than considering simplices, another higher-dimensional version adds another and asks for placements of formula_1 points in the unit hypercube that maximize the minimum volume  of the convex hull of any subset of formula_36 points. For formula_37 these subsets form simplices but for larger values relative they can form more complicated shapes. When formula_36 is sufficiently large relative randomly placed point sets have minimum convex hull No better bound is possible; any placement has formula_36 points with obtained by choosing some formula_36 consecutive points in coordinate order. This result has applications in range searching data structures.