Disjoint empty disks supported by a point set

DOI10.1007/S00022-013-0160-8zbMATH Open1278.52009arXiv1203.0563OpenAlexW2031312788MaRDI QIDQ375386FDOQ375386

Authors: Adrian Dumitrescu, Minghui Jiang 

Publication date: 30 October 2013

Published in: Journal of Geometry (Search for Journal in Brave)

Abstract: For a planar point-set $P$, let D(P) be the minimum number of pairwise-disjoint empty disks such that each point in $P$ lies on the boundary of some disk. Further define D(n) as the maximum of D(P) over all n-element point sets. Hosono and Urabe recently conjectured that $D(n)=lceiln/2ceil$. Here we show that $D(n)geqn/2+n/236-O(sqrtn)$ and thereby disprove this conjecture.

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

Recommendations

• Disjoint empty convex polygons in planar point sets
• Cutting a set of disks by a line with leaving many intact disks in both sides
• scientific article; zbMATH DE number 1150145
• On the minimum size of a point set containing a 5-hole and double disjoint 3-holes
• Disjoint empty convex pentagons in planar point sets

zbMATH Keywords

graphconnected componentempty diskpoint-circle incidence

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Cites Work

• Toughness and Delaunay triangulations
• Matching points with squares
• Maximum area independent sets in disk intersection graphs
• Disjoint empty disks supported by a point set
• Title not available (Why is that?)
• A Minimal Planar Point Set with Specified Disjoint Empty Convex Subsets
• Matching Points with Circles and Squares
• Title not available (Why is that?)
• On covering problems of Rado

Cited In (1)

• Disjoint empty disks supported by a point set

This page was built for publication: Disjoint empty disks supported by a point set

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