Disjoint empty disks supported by a point set

DOI10.1007/S00022-013-0160-8MaRDI QIDQ375386zbMATHOpenAlexFDO

Authors Adrian Dumitrescu, Minghui Jiang

Publication date 30 October 2013

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

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

zbMATH Keywords

graphconnected componentempty diskpoint-circle incidence

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 903282 (Why is no real title available?)
• scientific article; zbMATH DE number 3408456 (Why is no real title available?)
• A Minimal Planar Point Set with Specified Disjoint Empty Convex Subsets
• Disjoint empty disks supported by a point set
• Matching Points with Circles and Squares
• Matching points with squares
• Maximum area independent sets in disk intersection graphs
• On covering problems of Rado
• Toughness and Delaunay triangulations

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)