Stabbing pairwise intersecting disks by four points

DOI10.1007/S00454-023-00567-0MaRDI QIDQ6142366zbMATH OpenFDO

Authors Paz Carmi, Matthew J. Katz, Pat Morin

Publication date 21 December 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

disks in the planeHelly-type theoremspiercing set

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: In their seminal work, Danzer (1956, 1986) and Stach'{o} (1981) established that every set of pairwise intersecting disks in the plane can be stabbed by four points. However, both these proofs are non-constructive, at least in the sense that they do not seem to imply an efficient algorithm for finding the stabbing points, given such a set of disks $D$. Recently, Har-Peled etal (2018) presented a relatively simple linear-time algorithm for finding five points that stab $D$. We present an alternative proof (and the first in English) to the assertion that four points are sufficient to stab $D$. Moreover, our proof is constructive and provides a simple linear-time algorithm for finding the stabbing points. As a warmup, we present a nearly-trivial liner-time algorithm with an elementary proof for finding five points that stab $D$.

Recommendations

• Stabbing pairwise intersecting disks by five points
• Stabbing pairwise intersecting disks by five points
• Simple linear time algorithms for piercing pairwise intersecting disks
• Piercing pairwise intersecting geodesic disks by five points
• Stabbing circles for sets of segments in the plane

Cites work

• A subexponential bound for linear programming
• Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene
• 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 3219448 (Why is no real title available?)
• Largest bounding box, smallest diameter, and related problems on imprecise points
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Stabbing pairwise intersecting disks by five points

Cited in

(6)

• Stabbing pairwise intersecting disks by five points
• Piercing diametral disks induced by edges of maximum spanning trees
• Euclidean maximum matchings in the plane -- local to global
• Piercing unit geodesic disks
• The maximum clique problem in a disk graph made easy
• Dynamic maximum depth of geometric objects

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

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