POINTS AND TRIANGLES IN THE PLANE AND HALVING PLANES IN SPACE

被引：36

作者：

ARONOV, B

CHAZELLE, B

EDELSBRUNNER, H

GUIBAS, LJ

SHARIR, M

WENGER, R

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

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

[3] DEC SYST RES CTR,PALO ALTO,CA 94301

[4] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

[5] TEL AVIV UNIV,SACKLER FAC EXACT SCI,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1991年 / 6卷 / 05期

关键词：

D O I：

10.1007/BF02574700

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that for any set S of n points in the plane and n3-alpha triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n3-3-alpha/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most cube-root (c/2)n8/3 log5/3 n halving planes.

引用

页码：435 / 442

页数：8

共 12 条

[1] THE NUMBER OF SMALL SEMISPACES OF A FINITE-SET OF POINTS IN THE PLANE [J].