On circles enclosing many points

DOI10.1016/J.DISC.2021.112541MaRDI QIDQ2043403zbMATH OpenOpenAlexWikidataFDO

Authors Mercè Claverol, Clemens Huemer, Alejandra Martínez-Moraian

Publication date 2 August 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

circle containmentdiscrete geometrypoint setVoronoi diagram

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Euclidean geometries (general) and generalizations (51M05) Geometric constructions in real or complex geometry (51M15) Convex sets in (2) dimensions (including convex curves) (52A10)

Abstract: We prove that every set of $n$ red and $n$ blue points in the plane contains a red and a blue point such that every circle through them encloses at least $n(1-frac1sqrt2)-o(n)$ points of the set. This is a two-colored version of a problem posed by Neumann-Lara and Urrutia. We also show that every set $S$ of $n$ points contains two points such that every circle passing through them encloses at most $lfloorfrac2n-33floor$ points of $S$. The proofs make use of properties of higher order Voronoi diagrams, in the spirit of the work of Edelsbrunner, Hasan, Seidel and Shen on this topic. Closely related, we also study the number of collinear edges in higher order Voronoi diagrams and present several constructions.

Recommendations

• On enclosing k points by a circle
• On circles containing the maximum number of points
• Point sets with many unit circles
• Circles through two points that always enclose many points
• On the number of circles determined byn points
• scientific article; zbMATH DE number 3863993
• Some extremal results on circles containing points
• On the number of ordinary circles determined by \(n\) points
• On the number of circles determined by \(n\) points in the Euclidean plane

Cites work

• A combinatorial property of points and balls, a colored version
• 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
• Depth of segments and circles through points enclosing many points: A note
• scientific article; zbMATH DE number 2086212 (Why is no real title available?)
• scientific article; zbMATH DE number 751132 (Why is no real title available?)
• scientific article; zbMATH DE number 2102914 (Why is no real title available?)
• Improved bounds for planar k-sets and related problems
• On `\(k\)-sets' in the plane
• On Center Regions and Balls Containing Many Points
• On circles containing the maximum number of points
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Some extremal results on circles containing points
• The Number of Halving Circles
• The number of small semispaces of a finite set of points in the plane

Cited in

(11)

• Depth of segments and circles through points enclosing many points: A note
• Point sets with many unit circles
• Circles through two points that always enclose many points
• On the number of circles determined by \(n\) points in the Euclidean plane
• On the geometry of the smallest circle enclosing a finite set of points
• scientific article; zbMATH DE number 3863993 (Why is no real title available?)
• scientific article; zbMATH DE number 1098778 (Why is no real title available?)
• scientific article; zbMATH DE number 2103167 (Why is no real title available?)
• On the number of ordinary circles determined by \(n\) points
• On polynomials associated to Voronoi diagrams of point sets and crossing numbers
• On geodesic disks enclosing many points

This page was built for publication: On circles enclosing many points

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