Editing Heilbronn triangle problem (section)

==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.{{r|jlv|grimmett}} Variations involving the volume of higher-dimensional [[simplex|simplices]] have also been studied.{{r|brass|lefmann|barnao}}

Rather than considering simplices, another higher-dimensional version adds another {{nowrap|parameter <math>k</math>,}} and asks for placements of <math>n</math> points in the unit [[hypercube]] that maximize the minimum volume of the [[convex hull]] of any subset of <math>k</math> points. For <math>k=d+1</math> these subsets form simplices but for larger values {{nowrap|of <math>k</math>,}} relative {{nowrap|to <math>d</math>,}} they can form more complicated shapes. When <math>k</math> is sufficiently large relative {{nowrap|to <math>\log n</math>,}} randomly placed point sets have minimum {{nowrap|<math>k</math>-point}} convex hull {{nowrap|volume <math>\Omega(k/n)</math>.}} No better bound is possible; any placement has <math>k</math> points with {{nowrap|volume <math>O(k/n)</math>,}} obtained by choosing some <math>k</math> consecutive points in coordinate order. This result has applications in [[range searching]] data structures.{{r|chazelle}}