Questions tagged [polygon]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
80 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 ...
1
vote
1answer
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 ...
10
votes
1answer
116 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$...
7
votes
0answers
298 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 ...
3
votes
3answers
373 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 ...
22
votes
2answers
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 ...
9
votes
2answers
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 ...
-4
votes
1answer
213 views

Sweeping a Polygon With Holes

I am looking for a algorithm or an idea for a algorithm for triangulation a polygon with holes (one outer polygon P containing several polygonal holes) via plane sweep. The diagonals should ...
4
votes
7answers
530 views

Menagerie of polygons

UPDATE Now community wiki. My new version of the question is: let's make a big list of classes of polygons. We may be able to produce the most comprehensive list on the web, or in the literature. ...