Approximating Maximum Independent Set for Rectangles in the Plane

Algorithms Seminar
Speaker Name
Joe Mitchell
Date and Time
-
Location
The talk will be virtual on Zoom.
Notes
The Zoom link will be emailed to CS faculty/grad students, or contact Jennifer Schmidt (jschmidt at cs.duke.edu) to request it.
Abstract

Given a set ${\cal R}=\{R_1,\ldots,R_n\}$ of $n$ axis-aligned rectangles in the plane, the {\em maximum independent set of rectangles} (MISR) problem seeks a maximum-cardinality subset, ${\cal R}^*\subseteq {\cal R}$, of rectangles that are {\em independent}, meaning that any two rectangles of ${\cal R}^*$ are interior-disjoint. The MISR, which is known to be NP-hard, has geometric structure that enables approximation algorithms with far better performance than is known (or even possible) for maximum independent set in a general graph. In particular, a polynomial-time approximation scheme (PTAS) is possible for MISR if the rectangles are ``fat'' (have a bounded aspect ratio), a quasipolynomial-time approximation scheme (QPTAS) is possible in general, and an $O(\log\log n)$-approximation algorithm is known that runs in polynomial time.  In this talk, we present a polynomial-time constant-factor approximation algorithm for MISR.  The result is based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned in a constant number of such subfaces.

(see https://arxiv.org/abs/2101.00326)

Short Biography

Joe Mitchell is one of the country’s leaders in computational geometry, which studies the design, analysis, and implementation of efficient algorithms to solve geometric problems. His particular interest is applications to problems in computer graphics, visualization, robotics, manufacturing, geographic information systems, and computer vision.  He is (Chair) Distinguished Professor of Applied Mathematics & Statistics at Stony Brook University.