# Questions tagged [polygon]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
139 views

### Convex polygons inclusion relation

I have the following problem which came as a subproblem in some work I was doing and I am completely stuck. Note that I am interested in it only in terms of worst case time complexity (not heuristics ...
115 views

### Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
60 views

### Finding a point outside of each of a set of polygons in a bounded space

I know there are algorithms for finding a point inside a simple polygon. Given a set of polygons inside a rectangle (think a bunch of polygons on a computer screen), is there an efficient algorithm ...
136 views

### Minimum equidecomposable decomposition

Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all $i$...
320 views

### Minimum length cuts needed to remove holes in a polygon

Suppose I'm given a connected polygon in the plane with holes. I can "remove" a hole by drawing a straight line from the boundary of a hole to another boundary (either of another hole, or the boundary ...
379 views

### Partitioning a set of 2d polygons into intersection-connected subsets

My question is given a set of 2d polygons how can I find the connected components of polygons according to a criteria based on intersection or proximity of them. In other words I have a set of ...
1k views

### Detecting two kinds of almost-simple polygons

I'm interested in the complexity of deciding whether a given non-simple polygon is almost simple, in either of two different formal senses: weakly simple or non-self-crossing. Since these terms are ...
1k views

### Polygon within polygon generalization problem

I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical ...