A combinatorial property of convex sets
type: Item
instance of: scholarly article
title: A combinatorial property of convex sets
zbMATH Open document ID: 0872.52003
DOI: 10.1007/PL00009296
author: Manuel Abellanas
author: V. Neumann-Lara
author: J. Urrutia
author: Gregorio Hernández
author: Rolf Klein
published in: Discrete \& Computational Geometry
publication date: 1997-09-23T00:00:00Z
review text: A known result in combinatorial geometry states that in any set \(P_n\) of \(n\) points in the plane there are two elements such that any circle containing them contains \(n/c\) elements of \(P_n\), \(c\) a constant. This has already previously been generalized to higher dimensions. Here the authors prove a generalization of the original result in a different direction. The set \(P_n\) is replaced by a family \(\Phi \) of \(n\) noncrossing compact convex sets, and ''circle'' is replaced by ''homethetic image of a fixed strictly convex compact set \(S\)''. By constructing a counterexample they show that the word ''noncrossing'' must not be omitted, and that the analogue in higher dimensions does not even hold for families of disjoint compact convex sets. The proof is based on a new kind of Voronoi diagram, the so-called ''closest covered set Voronoi diagram'', where each point \(x\) of the plane belongs to the cell of the first element of \(\Phi \) contained in an expanding homothetic image of \(S\) centered at \(x\).
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 52A10
zbMATH DE Number: 1011311
zbMATH Keywords: Voronoi diagram
zbMATH Keywords: containment problems
zbMATH Keywords: circle orders
reviewed by: Johann Linhart
MaRDI profile type: Publication
cites work: A combinatorial property of points and ellipsoids
cites work: A combinatorial result about points and balls in Euclidean space
cites work: Circles through two points that always enclose many points
cites work: Interval orders and circle orders
cites work: A note on the circle containment problem
cites work: Some extremal results on circles containing points
cites work: Randomized incremental construction of abstract Voronoi diagrams
cites work: A combinatorial result on points and circles on the plane
cites work: Q4918394
description: scientific article; zbMATH DE number 1011311