Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### 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 ...
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 ...
• 9,626
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 ...
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 ...
• 1,153
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$...
• 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$...
• 5,772

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