Simple linear time algorithms for piercing pairwise intersecting disks

DOI10.1016/J.COMGEO.2023.102011MaRDI QIDQ6110069zbMATH OpenFDO

Authors Ahmad Biniaz, Prosenjit Bose, Yunkai Wang

Publication date 31 July 2023

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COMGEO.2023.102011

zbMATH Keywords

disksgeometric transformationspiercing sets

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Helly-type theorems and geometric transversal theory (52A35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Piercing pairwise intersecting geodesic disks
• Stabbing pairwise intersecting disks by five points
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• On piercing sets of axis-parallel rectangles and rings
• ON PIERCING SETS OF AXIS-PARALLEL RECTANGLES AND RINGS

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 49381 (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
• Piercing pairwise intersecting geodesic disks
• Stabbing pairwise intersecting disks by five points
• Stabbing pairwise intersecting disks by five points

Cited in

(12)

• Intersection queries in sets of disks
• Stabbing pairwise intersecting disks by five points
• Piercing pairwise intersecting geodesic disks
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• scientific article; zbMATH DE number 1254001 (Why is no real title available?)
• ON PIERCING SETS OF AXIS-PARALLEL RECTANGLES AND RINGS
• Stabbing pairwise intersecting disks by five points
• Stabbing pairwise intersecting disks by four points
• Piercing pairwise intersecting convex shapes in the plane
• Piercing diametral disks induced by edges of maximum spanning trees
• Piercing unit geodesic disks
• On piercing sets of axis-parallel rectangles and rings

This page was built for publication: Simple linear time algorithms for piercing pairwise intersecting disks

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