Stabbing pairwise intersecting disks by five points

DOI10.1016/j.disc.2021.112403zbMath1466.52004arXiv1801.03158OpenAlexW2784250110MaRDI QIDQ2032723

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

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

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)

Related Items (max. 100)

Euclidean maximum matchings in the plane -- local to global ⋮ On maximum-sum matchings of points ⋮ Piercing diametral disks induced by edges of maximum spanning trees ⋮ Simple linear time algorithms for piercing pairwise intersecting disks ⋮ Stabbing pairwise intersecting disks by four points ⋮ Unnamed Item ⋮ Piercing pairwise intersecting geodesic disks ⋮ Piercing pairwise intersecting geodesic disks by five points

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Piercing translates and homothets of a convex body
• Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene
• Unit disk graphs
• Small-dimensional linear programming and convex hulls made easy
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• The clique problem in intersection graphs of ellipses and triangles
• 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
• Reducibility among Combinatorial Problems

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