Depth of segments and circles through points enclosing many points: A note

DOI10.1016/J.COMGEO.2008.07.001MaRDI QIDQ1005330zbMATH OpenOpenAlexFDO

Authors Pedro Ramos, Raquel Viaña

Publication date 9 March 2009

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.1088

zbMATH Keywords

circle containmentdiscrete geometrysegment depth

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Abstract: Neumann-Lara and Urrutia showed in 1985 that in any set of n points in the plane in general positionthere is always a pair of points such that any circle through them contains at least (n-2)/60 points. In a series of papers, this result was subsequently improved till n/4.7, which is currently the best known lower bound. In this paper we propose a new approach to the problem that allows us, by using known results about j-facets of sets of points in $R^3$, to give a simple proof of a somehow stronger result: there is always a pair of points such that any circle through them has, both inside and outside, at least n/4.7 points.

Recommendations

• A note on the circle containment problem
• Some extremal results on circles containing points
• A combinatorial result on points and circles on the plane
• Circles through two points that always enclose many points
• On circles enclosing many points

Cites work

• A combinatorial result about points and balls in Euclidean space
• A combinatorial result on points and circles on the plane
• A note on the circle containment problem
• Applications of random sampling in computational geometry. II
• Circles through two points that always enclose many points
• scientific article; zbMATH DE number 2086212 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• On Center Regions and Balls Containing Many Points
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Some extremal results on circles containing points

Cited in

(8)

• Points with large \(\alpha \)-depth
• Some extremal results on circles containing points
• A note on the circle containment problem
• Circles through two points that always enclose many points
• On circles enclosing many points
• Tukey depth histograms
• On geodesic disks enclosing many points
• Polychromatic coloring of tuples in hypergraphs

This page was built for publication: Depth of segments and circles through points enclosing many points: A note

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1005330)