forgot password?
register here
Research articles
  search articles
  reviews guidelines
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
Members: 2981
Articles: 2'033'011
Articles rated: 2577

25 January 2021
  » arxiv » math.CO/9902043

 Article overview

The Average-Case Area of Heilbronn-Type Triangles
Tao Jiang ; Ming Li ; Paul Vitanyi ;
Date 5 Feb 1999
Journal T. Jiang, M. Li, and P. Vitanyi, The average-case area of Heilbronn-type triangles, Random Structures and Algorithms, 20:2(2002), 206-219
Subject Combinatorics; Logic; Metric Geometry; Probability; Computational Geometry; Discrete Mathematics MSC-class: 52C10 | math.CO cs.CG cs.DM math.LO math.MG math.PR
AffiliationUCR), Ming Li (UCSB), Paul Vitanyi (CWI and U Amsterdam
AbstractFrom among $ {n choose 3}$ triangles with vertices chosen from $n$ points in the unit square, let $T$ be the one with the smallest area, and let $A$ be the area of $T$. Heilbronn’s triangle problem asks for the maximum value assumed by $A$ over all choices of $n$ points. We consider the average-case: If the $n$ points are chosen independently and at random (with a uniform distribution), then there exist positive constants $c$ and $C$ such that $c/n^3 < mu_n < C/n^3$ for all large enough values of $n$, where $mu_n$ is the expectation of $A$. Moreover, $c/n^3 < A < C/n^3$, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in ``general position.’’
Source arXiv, math.CO/9902043
Services Forum | Review | PDF | Favorites   
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
of broad interest:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser CCBot/2.0 (
» my Online CV
» Free

News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2021 - Scimetrica