Lune

FOCS2023Top-tier venue

Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon

Reilly Browne, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, Valentin Polishchuk

Abstract

Given a simple polygon P , the minimum convex cover problem seeks to cover P with the fewest convex polygons that lie within P . The maximum hidden set problem seeks to place within P a maximum cardinality set of points no two of which see each other. We give constant factor approximation algorithms for both problems. Previously, the best approximation factor for the minimum convex cover was logarithmic; for the maximum hidden set problem, no approximation algorithm was known.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Peeling Rotten Potatoes for a Faster Approximation of Convex Cover cites Covering Polygons is Even Harder
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Peeling Rotten Potatoes for a Faster Approximation of Convex CoverOmrit Filtser, Tzalik Maimon, Ofir YomtovyanSODA 2026

Builds on4

  1. Maximum Flow and Minimum-Cost Flow in Almost-Linear TimeLi Chen, Rasmus Kyng, Yang P. Liu, Richard Peng et al.FOCS 2022 · 135 citations
  2. Covering Polygons is Even HarderMikkel AbrahamsenFOCS 2021 · 25 citations
  3. Approximating Maximum Independent Set for Rectangles in the PlaneJoseph S. B. MitchellFOCS 2021 · 18 citations
  4. A 3-Approximation Algorithm for Maximum Independent Set of RectanglesWaldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke et al.SODA 2022 · 16 citations

Related papers

  1. Economical Convex Coverings and ApplicationsSunil Arya, Guilherme Dias da Fonseca, David M. MountSODA 2023 · 1 citation
  2. Hardness of Packing, Covering and Partitioning Simple Polygons with Unit SquaresMikkel Abrahamsen, Jack StadeFOCS 2024 · 2 citations
  3. Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and MatchingSujoy Bhore, Timothy M. ChanSODA 2025 · 4 citations
  4. Non-uniform Geometric Set Cover and Scheduling on Multiple MachinesNikhil Bansal, Jatin BatraSODA 2021 · 4 citations
  5. Minimum Star Partitions of Simple Polygons in Polynomial TimeMikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen ZhangSTOC 2024 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines