Stabbing pairwise intersecting disks by five points

DOI10.1016/J.DISC.2021.112403MaRDI QIDQ2032723zbMATH OpenOpenAlexFDO

Authors Sariel Har-Peled, Wolfgang Mulzer, Paul Seiferth, Max Willert, Haim Kaplan, Liam Roditty, Micha Sharir

Publication date 14 June 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.03158, https://drops.dagstuhl.de/opus/volltexte/2018/9998/

zbMATH Keywords

LP-type problemdisk intersection graphstabbing set

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10) Elementary problems in Euclidean geometries (51M04)

Abstract: Suppose we are given a set $mathcalD$ of $n$ pairwise intersecting disks in the plane. A planar point set $P$ stabs $mathcalD$ if and only if each disk in $mathcalD$ contains at least one point from $P$. We present a deterministic algorithm that takes $O(n)$ time to find five points that stab $mathcalD$. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points. Moreover, we present a simple argument showing that eight disks can be stabbed by at most three points. This provides a simple-albeit slightly weaker-algorithmic version of a classical result by Danzer that such a set $mathcalD$ can always be stabbed by four points.

Recommendations

• Simple linear time algorithms for piercing pairwise intersecting disks
• Piercing pairwise intersecting geodesic disks
• Stabbing circles for sets of segments in the plane
• Stabbing circles for sets of segments in the plane
• scientific article; zbMATH DE number 7662166

Cites work

• scientific article; zbMATH DE number 4017764 (Why is no real title available?)
• scientific article; zbMATH DE number 3156887 (Why is no real title available?)
• scientific article; zbMATH DE number 3971629 (Why is no real title available?)
• scientific article; zbMATH DE number 6469174 (Why is no real title available?)
• scientific article; zbMATH DE number 3219448 (Why is no real title available?)
• Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Piercing translates and homothets of a convex body
• Reducibility among combinatorial problems
• Small-dimensional linear programming and convex hulls made easy
• The clique problem in intersection graphs of ellipses and triangles
• Unit disk graphs

Cited in

(10)

• Piercing pairwise intersecting geodesic disks
• Euclidean maximum matchings in the plane -- local to global
• On maximum-sum matchings of points
• Stabbing pairwise intersecting disks by four points
• scientific article; zbMATH DE number 7662166 (Why is no real title available?)
• Piercing diametral disks induced by edges of maximum spanning trees
• Piercing diametral disks induced by edges of maximum spanning trees
• Simple linear time algorithms for piercing pairwise intersecting disks
• Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
• Piercing pairwise intersecting geodesic disks by five points

This page was built for publication: Stabbing pairwise intersecting disks by five points

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