Questions tagged [polygon]
The polygon tag has no usage guidance.
15 questions
1
vote
0
answers
125
views
Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments
Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
- 21.1k
2
votes
1
answer
442
views
Complexity of polygon intersection test
In the book "Spatial Databases: With Application to GIS (The Morgan Kaufmann Series in Data Management Systems)", there's a section on simple polygon intersection detection , and it mentions
...
- 123
0
votes
0
answers
89
views
A Simpler Solution for a special case of the Set Cover problem
We decomposed a simple polygon into many small regions. Then we estimated a visibility polygon of a point by a subset of the small regions. Now I need the minimum set of visibility polygons that can ...
- 21
2
votes
2
answers
298
views
Partitioning a connected polygon into connected pieces of equal area
Armaselu and Daescu (TCS, 2015) present algorithms that, given a convex polygon $P$ and an integer $m$ (which must be a power of $2$), return a partition of $P$ into $m$ convex polygons with the same ...
- 2,314
0
votes
1
answer
85
views
How hard is deciding the existence of a polygonization with prescribed perimeter?
Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or ...
- 21.1k
3
votes
1
answer
247
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 ...
- 41
3
votes
1
answer
157
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 ...
- 21.1k
1
vote
1
answer
69
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 ...
- 299
10
votes
1
answer
149
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
0
answers
382
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 ...
- 32.2k
3
votes
3
answers
445
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 ...
- 384
22
votes
2
answers
2k
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 ...
- 23.3k
9
votes
2
answers
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
1
answer
335
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 ...
- 233
4
votes
7
answers
553
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. ...