COUNTING TRIANGLE CROSSINGS AND HALVING PLANES

被引：37

作者：

DEY, TK ^{[1
]}

EDELSBRUNNER, H ^{[1
]}

机构：

[1] UNIV ILLINOIS,DEPT COMP SCI,URBANA,IL 61801

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1994年 / 12卷 / 03期

关键词：

D O I：

10.1007/BF02574381

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Every collection of t greater than or equal to 2n(2) triangles with a total of n vertices in R(3) has Omega(t(4)/n(6)) crossing pairs. This implies that one of their edges meets Omega(t(3)/n(6)) of the triangles. From this it follows that n points in R(3) have only O(n(8/3)) halving planes.

引用

页码：281 / 289

页数：9

共 9 条

[1]

Ajtai M., 1982, ANN DISCRETE MATH, V12, P9

[2]

Alon N., 1992, COMB PROBAB COMPUT, V1, P189

[3]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[4] POINTS AND TRIANGLES IN THE PLANE AND HALVING PLANES IN SPACE [J].

ARONOV, B ;

CHAZELLE, B ;

EDELSBRUNNER, H ;

GUIBAS, LJ ;

SHARIR, M ;

WENGER, R .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :435-442

[5]

BARANY I, 1989, 5TH P ANN S COMP GEO, P140

[6] IMPROVED BOUNDS FOR INTERSECTING TRIANGLES AND HALVING PLANES [J].

EPPSTEIN, D .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1993, 62 (01) :176-182

[7]

ERDOS P, 1973, SURVEY COMBINATORIAL, P1398

[8] Amounts of convex bodies which contain a common point [J].

Radon, J .

MATHEMATISCHE ANNALEN, 1921, 83 :113-115

[9]

ZIVALJEVIC RT, 1992, J COMB THEORY A, V61, P309

← 1 →