Points and triangles in the plane and halving planes in space

Boris Aronov; Bernard Chazelle; Herbert Edelsbrunner; Leonidas J. Guibas; Micha Sharir; Rephael Wenger

doi:10.1007/BF02574700

Points and triangles in the plane and halving planes in space

Boris Aronov, Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Rephael Wenger

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that for any set S of n points in the plane and n^3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n^3-3α/(c log⁵ n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.

Original language	English (US)
Pages (from-to)	435-442
Number of pages	8
Journal	Discrete & Computational Geometry
Volume	6
Issue number	1
DOIs	https://doi.org/10.1007/BF02574700
State	Published - Dec 1991

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/BF02574700

Cite this

@article{215b94dd597a4de3a0ce793d7aedde5d,

title = "Points and triangles in the plane and halving planes in space",

abstract = "We prove that for any set S of n points in the plane and n 3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n 3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.",

author = "Boris Aronov and Bernard Chazelle and Herbert Edelsbrunner and Guibas, {Leonidas J.} and Micha Sharir and Rephael Wenger",

year = "1991",

month = dec,

doi = "10.1007/BF02574700",

language = "English (US)",

volume = "6",

pages = "435--442",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Points and triangles in the plane and halving planes in space

AU - Aronov, Boris

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas J.

AU - Sharir, Micha

AU - Wenger, Rephael

PY - 1991/12

Y1 - 1991/12

N2 - We prove that for any set S of n points in the plane and n 3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n 3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.

AB - We prove that for any set S of n points in the plane and n 3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n 3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.

UR - http://www.scopus.com/inward/record.url?scp=51249171292&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249171292&partnerID=8YFLogxK

U2 - 10.1007/BF02574700

DO - 10.1007/BF02574700

M3 - Article

AN - SCOPUS:51249171292

SN - 0179-5376

VL - 6

SP - 435

EP - 442

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

Points and triangles in the plane and halving planes in space

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this