Point sets in the unit square and large areas of convex hulls of subsets of points |
| |
Authors: | Hanno Lefmann |
| |
Institution: | 1.Fakult?t für Informatik,TU Chemnitz,Chemnitz,Germany |
| |
Abstract: | In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square 0,1]2 are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n
6k−4) time algorithm is given, which finds distributions of n points in 0,1]2 such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)1/(j−2)/n
(j−1)/(j−2)). |
| |
Keywords: | Heilbronn’ s triangle problem Approximation algorithm Hypergraphs |
本文献已被 SpringerLink 等数据库收录! |
|