On some geometric optimization problems with segments

DOI10.1016/J.TCS.2025.115364MaRDI QIDQ6956050zbMATH OpenFDO

Authors Joseph S. B. Mitchell, Supantha Pandit

Publication date 21 July 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115364

zbMATH Keywords

dominating setNP-completenessindependent setsegmentsgeometric set coverinclined linepiercing set

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites work

• A 3-approximation algorithm for maximum independent set of rectangles
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Approximating maximum independent set for rectangles in the plane
• Combinatorial optimization. Networks and matroids
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• Geometric hitting set for segments of few orientations
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• On dominating set of some subclasses of string graphs
• Optimal binary space partitions for segments in the plane
• Orthogonal segment stabbing
• Packing and covering with segments

This page was built for publication: On some geometric optimization problems with segments

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