Seminars

View all Seminars  |  Download ICal for this event

Hardness of Packing Simple Polygons with Unit Squares

Series: Bangalore Theory Seminars

Speaker: Jack Tor Stade, Datalogisk Institut, University of Copenhagen

Date/Time: Aug 30 17:00:00

Location: Online Talk (See Teams link below)

Abstract:
We show that packing axis-aligned unit squares into a simple polygon $P$ is NP-hard, even when $P$ is an orthogonal and orthogonally convex polygon with half-integer vertices.

It has been known since the early 80s that packing unit squares into a polygon with holes is NP-hard~[Fowler, Paterson, Tanimoto, Inf. Process. Lett., 1981], but the version without holes was conjectured to be in P more than two decades ago~[Baur and Fekete, Algorithmica, 2001].

Our construction uses a new way of reducing from textsc{Planar-3SAT}. Interestingly, our geometric realization of a planar formula is non-planar. Vertices become rows and edges become columns, with crossings being allowed. The planarity of the graph ensures that the polygon does not have holes.

These ideas can also be used to show hardness of some closely related covering and partitioning problems.

Microsoft teams link:

Link

We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar