Points and triangles in the plane and halving planes in space

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

doi:10.1145/98524.98548

Points and triangles in the plane and halving planes in space

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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

Original language	English (US)
Title of host publication	Proc Sixth Annu Symp Comput Geom
Publisher	Publ by ACM
Pages	112-115
Number of pages	4
ISBN (Print)	0897913620, 9780897913621
DOIs	https://doi.org/10.1145/98524.98548
State	Published - 1990
Event	Proceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA Duration: Jun 6 1990 → Jun 8 1990

Publication series

Name	Proc Sixth Annu Symp Comput Geom

Conference

Conference	Proceedings of the Sixth Annual Symposium on Computational Geometry
City	Berkeley, CA, USA
Period	6/6/90 → 6/8/90

ASJC Scopus subject areas

General Engineering

Access to Document

10.1145/98524.98548

Cite this

Aronov, B, Guibas, LJ, Chazelle, B, Sharir, M, Edelsbrunner, H & Wenger, R 1990, Points and triangles in the plane and halving planes in space. in Proc Sixth Annu Symp Comput Geom. Proc Sixth Annu Symp Comput Geom, Publ by ACM, pp. 112-115, Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, 6/6/90. https://doi.org/10.1145/98524.98548

@inproceedings{197aaf35e7a74fb6afea5d815e84e9b0,

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 n3-α triangles spanned by the points of S there exists a point (not necessarily of S) contained in at least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.",

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

year = "1990",

doi = "10.1145/98524.98548",

language = "English (US)",

isbn = "0897913620",

series = "Proc Sixth Annu Symp Comput Geom",

publisher = "Publ by ACM",

pages = "112--115",

booktitle = "Proc Sixth Annu Symp Comput Geom",

note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",

}

TY - GEN

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

AU - Aronov, Boris

AU - Guibas, Leonidas J.

AU - Chazelle, Bernard

AU - Sharir, Micha

AU - Edelsbrunner, Herbert

AU - Wenger, Rephael

PY - 1990

Y1 - 1990

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

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

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

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

U2 - 10.1145/98524.98548

DO - 10.1145/98524.98548

M3 - Conference contribution

AN - SCOPUS:0025028278

SN - 0897913620

SN - 9780897913621

T3 - Proc Sixth Annu Symp Comput Geom

SP - 112

EP - 115

BT - Proc Sixth Annu Symp Comput Geom

PB - Publ by ACM

T2 - Proceedings of the Sixth Annual Symposium on Computational Geometry

Y2 - 6 June 1990 through 8 June 1990

ER -

Points and triangles in the plane and halving planes in space

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this