Large triangles in the d-dimensional unit-cube

被引:0
作者
Lefmann, H [1 ]
机构
[1] TU Chemnitz, Fak Informat, D-09107 Chemnitz, Germany
来源
COMPUTING AND COMBINATORICS, PROCEEDINGS | 2004年 / 3106卷
关键词
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We consider a variant of Heilbronn's triangle problem by asking for fixed dimension d greater than or equal to 2 for a distribution of n points in the d-dimensional unit-cube [0, 1](d) such that the minimum (2-dimensional) area of a triangle among these n points is maximal. Denoting this maximum value by Delta(d)(off-line) (n) and Delta(d)(on-line) (n) for the off-line and the on-line situation, respectively, we will show that c(1) (.)(log n)(1/(d-1)) /n(2/(d-1)) less than or equal to Delta(d)(off-line)(n) less than or equal to C-1/n(2/d) and c(2)/n(2/(d-1)) less than or equal to Delta(d)(on-line)(n) less than or equal to C-2/n(2/d) for constants c(1), c(2), C-1, C-2 > 0 which depend on d only.
引用
收藏
页码:43 / 52
页数:10
相关论文
共 21 条
  • [1] EXTREMAL UNCROWDED HYPERGRAPHS
    AJTAI, M
    KOMLOS, J
    PINTZ, J
    SPENCER, J
    SZEMEREDI, E
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1982, 32 (03) : 321 - 335
  • [2] A lower bound for Heilbronn's triangle problem in d
    Barequet, G
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2001, 14 (02) : 230 - 236
  • [3] BAREQUET G, 2002, LNCS, V2387, P360
  • [4] The algorithmic aspects of uncrowded hypergraphs
    Bertram-Kretzberg, C
    Lefmann, H
    [J]. SIAM JOURNAL ON COMPUTING, 1999, 29 (01) : 201 - 230
  • [5] An algorithm for Heilbronn's problem
    Bertram-Kretzberg, C
    Hofmeister, T
    Lefmann, H
    [J]. SIAM JOURNAL ON COMPUTING, 2000, 30 (02) : 383 - 390
  • [6] BRASS P, 2003, UPPER BOUND DDIMENSI
  • [7] ON UNCROWDED HYPERGRAPHS
    DUKE, RA
    LEFMANN, H
    RODL, V
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (2-3) : 209 - 212
  • [8] Fundia AD, 1996, RANDOM STRUCT ALGOR, V8, P131, DOI 10.1002/(SICI)1098-2418(199603)8:2<131::AID-RSA4>3.0.CO
  • [9] 2-Z
  • [10] The average-case area of Heilbronn-type triangles
    Jiang, T
    Li, M
    Vitányi, P
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2002, 20 (02) : 206 - 219