Paper Info

Title | ||
---|---|---|

The average-case area of Heilbronn-type triangles |

Abstract | ||
---|---|---|

From among ??? 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/n3 µn C/n3 for all large enough values of n, where µn is the expectation of A. Moreover, c/n3 A C/n3, 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." |

Year | DOI | Venue |
---|---|---|

1999 | 10.1002/rsa.10024 | Clinical Orthopaedics and Related Research |

Keywords | DocType | Volume |

heilbronn-type triangle,positive constants c,t. heilbronn,incompressibility method,n point,average-case area,general position,n c,smallest triangle,kolmogorov complexity,smallest area,triangle problem,uniform distribution | Journal | 20 |

Issue | ISSN | Citations |

2 | T. Jiang, M. Li, and P. Vitanyi, The average-case area of
Heilbronn-type triangles, Random Structures and Algorithms, 20:2(2002),
206-219 | 10 |

PageRank | References | Authors |

0.77 | 6 | 3 |

Authors (3 rows)

Cited by (10 rows)

References (6 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Tao Jiang | 1 | 1809 | 155.32 |

Ming Li | 2 | 5595 | 829.00 |

Paul Vitányi | 3 | 2130 | 287.76 |