![Heilbronn square n=6](https://upload.wikimedia.org/wikipedia/commons/b/bc/Heilbronn_square_n%3D6.svg)
In
discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geome ...
and
discrepancy theory
In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of ''classical'' discrepancy theory, name ...
, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding
triangle
A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC.
In Euclidean geometry, an ...
s of small
area
Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape
A shape or figure is a graphics, graphical representation of an obje ...
. It is named after
Hans Heilbronn
Hans Arnold Heilbronn (8 October 1908 – 28 April 1975) was a mathematician.
Education
He was born into a German-Jewish family. He was a student at the universities of Berlin, Freiburg and Göttingen, where he met Edmund Landau, who supervised ...
, who
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...
d that, no matter how points are placed in a given area, the smallest triangle area will be at most
inversely proportional
In mathematics, two sequences of numbers, often experimental data, are proportional or directly proportional if their corresponding elements have a constant ratio, which is called the coefficient of proportionality or proportionality constan ...
to the
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...
of the number of points. His conjecture was proven false, but the
asymptotic growth In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to ...
rate of the minimum triangle area remains unknown.
Definition
The Heilbronn triangle problem concerns the placement of
points within a shape in the plane, such as the
unit square
In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and .
Cartesian coordinates
In a Cartesian coordinate ...
or the
unit disk
In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1:
:D_1(P) = \.\,
The closed unit disk around ''P'' is the set of points whose di ...
, for a given Each triple of points form the three vertices of a
triangle
A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC.
In Euclidean geometry, an ...
, 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
points be placed to maximize the area of the smallest
More formally, the shape may be assumed to be a
compact set
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
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,
is additionally a
convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
of nonzero area. When three of the placed points
lie on a line, they are considered as forming a
degenerate
Degeneracy, degenerate, or degeneration may refer to:
Arts and entertainment
* Degenerate (album), ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed
* Degenerate art, a term adopted in the 1920s by the Nazi Party i ...
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
points, rather than only a sequence of placements approaching optimality. The number
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
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 at least one triangle with area 1/8 or smaller. Therefore,
Although researchers have studied the value of
for specific shapes and specific small numbers of points, Heilbronn was concerned instead about its
asymptotic behavior
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as beco ...
: if the shape
is held fixed, but
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
the numbers
and
differ only by a constant factor, as any placement of
points within
can be scaled by an
affine transformation
In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.
More generally, ...
to fit changing the minimum triangle area only by a constant. Therefore, in bounds on the growth rate of
that omit the
constant of proportionality
In mathematics, two sequences of numbers, often experimental data, are proportional or directly proportional if their corresponding elements have a constant ratio, which is called the coefficient of proportionality or proportionality constant ...
of that growth, the choice of
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
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
, this can be expressed as the bound
![No-three-in-line](https://upload.wikimedia.org/wikipedia/commons/6/67/No-three-in-line.svg)
In the other direction,
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
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
The no-three-in-line problem in discrete geometry asks how many points can be placed in the n\times n grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introd ...
, on large sets of grid points with no three in a line, to describe these examples. As Erdős observed, when
is a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, the set of
points
on an
integer grid (for have no three collinear points, and therefore by
Pick's formula
In geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field ...
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
is not prime, then a similar construction using a prime number close to
achieves the same asymptotic lower
eventually disproved Heilbronn's conjecture, by using the
probabilistic method
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects fr ...
to find sets of points whose smallest triangle area is larger than the ones found by Erdős. Their construction involves the following steps:
*Randomly place
points in the unit square, for
*Remove all pairs of points that are unexpectedly close together.
*Prove that there are few remaining low-area triangles and therefore only a sublinear number of cycles formed by two, three, or four low-area triangles. Remove all points belonging to these cycles.
*Apply a
triangle removal lemma In graph theory, the graph removal lemma states that when a graph contains few copies of a given Subgraph (graph theory), subgraph, then all of the copies can be eliminated by removing a small number of edges.
The special case in which the subgraph ...
for 3-uniform
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
s of high
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
to show that, with high probability, the remaining points include a subset of
points that do not form any small-area triangles.
The area resulting from their construction grows asymptotically as
The proof can be
derandomized, leading to a
polynomial-time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
algorithm for constructing placements with this triangle area.
Upper bounds
Every set of
points in the unit square forms a triangle of area at most inversely proportional One way to see this is to
triangulate
In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points.
Applications
In surveying
Specifically in surveying, triangulation involves only angle me ...
the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
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
Klaus Friedrich Roth (29 October 1925 – 10 November 2015) was a German-born British mathematician who won the Fields Medal for proving Roth's theorem on the Diophantine approximation of algebraic numbers. He was also a winner of the De M ...
proved a stronger upper bound of the form
The best bound known to date is of the form
for some proven by .
Specific shapes and numbers
has investigated the optimal arrangements of
points in a square, for
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
In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.
More generally, ...
of the vertices of a
regular polygon
In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either convex p ...
. 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
In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or sta ...
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
In mathematics and computer science, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of algorithms and software for manipulating mathematical expressions ...
techniques.
The following are the best known solutions for 7–12 points in a unit square, found through
simulated annealing
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It ...
; the arrangement for seven points is known to be optimal.
Heilbronn triangles, 7 points in square.svg, 7 points in a square, all 8 minimal triangles shaded
Heilbronn triangles, 8 points in square.svg, 8 points in a square, 5 of 12 minimal triangles shaded
Heilbronn triangles, 9 points in square.svg, 9 points in a square, 6 of 11 minimal triangles shaded
Heilbronn triangles, 10 points in square.svg, 10 points in a square, 3 of 16 minimal triangles shaded
Heilbronn triangles, 11 points in square.svg, 11 points in a square, 8 of 28 minimal triangles shaded
Heilbronn triangles, 12 points in square.svg, 12 points in a square, 3 of 20 minimal triangles shaded
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
with area one, the
regular hexagon
In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°.
Regular hexagon
A '' regular hexagon'' has ...
is the one that for this shape, with six points optimally placed at the hexagon vertices. The convex shapes of unit area that maximize
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
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
or
Poisson approximation show that the
expected value
In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a l ...
of the minimum area is inversely proportional to the cube of the number of points. Variations involving the volume of higher-dimensional
simplices
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
have also been studied.
Rather than considering simplices, another higher-dimensional version adds another and asks for placements of
points in the unit
hypercube
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...
that maximize the minimum volume of the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of any subset of
points. For
these subsets form simplices but for larger values relative they can form more complicated shapes. When
is sufficiently large relative randomly placed point sets have minimum convex hull No better bound is possible; any placement has
points with obtained by choosing some
consecutive points in coordinate order. This result has applications in
range searching
In computer science, the range searching problem consists of processing a set ''S'' of objects, in order to determine which objects from ''S'' intersect with a query object, called the ''range''. For example, if ''S'' is a set of points correspond ...
data structures.
See also
*
Danzer set
In geometry, a Danzer set is a set of points that touches every convex body of unit volume. Ludwig Danzer asked whether it is possible for such a set to have bounded density. Several variations of this problem remain unsolved.
Density
One way t ...
, a set of points that avoids empty triangles of large area
Notes
References
External links
*{{mathworld, id=HeilbronnTriangleProblem, title=Heilbronn Triangle Problem, mode=cs2
Erich's Packing Center by Erich Friedman, including the best known solutions to the Heilbronn problem for small values of
for squares, circles, equilateral triangles, and convex regions of variable shape but fixed area
Discrete geometry
Triangle problems
Area
Discrepancy theory