Skip to main content
4 votes

Partitioning a connected polygon into connected pieces of equal area

To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the ...
David Eppstein's user avatar
3 votes
Accepted

Partitioning a connected polygon into connected pieces of equal area

There must be many ways to do it - here is one way... Compute the medial axis of the polygon using the $L_1$ metric. Any point on the boundary defines a natural segment that goes from this point to a ...
Sariel Har-Peled's user avatar
3 votes
Accepted

Convex polygons inclusion relation

Here's an argument that you need time quadratic in the number of polygons. More precisely, you should not be able to find containing pairs among $n$ $k$-sided polygons in time $O(n^{2-\epsilon})$, for ...
David Eppstein's user avatar
2 votes
Accepted

Complexity of polygon intersection test

TL;DR: Yes, in principle this can be done in $O(n)$ and the book is inaccurate. This is quite subtle, the first statement is not correct. Returning all intersections has a $\Omega(n\log n)$ lower ...
user3508551's user avatar
  • 1,153
2 votes
Accepted

Complexity of existence of simple polygonalization with prescribed area?

The answer to your question is already contained in Fekete's paper. In Section 3, Fekete shows that the following problem GRID-EMPTY is NP-complete: Problem: GRID-EMPTY Instance: a set $S$ of $n$...
Gamow's user avatar
  • 5,772
1 vote
Accepted

How hard is deciding the existence of a polygonization with prescribed perimeter?

Your problem is NP-hard, since it contains the Hamiltonian cycle problem on grid graphs as special case: Given a set of lattice points in the plane, is there a cycle in which all edges have lengths $1$...
Gamow's user avatar
  • 5,772

Only top scored, non community-wiki answers of a minimum length are eligible