All Questions
Tagged with computational-geometry polygons
21
questions
0
votes
1
answer
49
views
What is the most dense sample for which the Crust algorithm returns an incorrect polygonal reconstruction?
The Crust algorithm by Amenta, Bern, and Eppstein computes a polygonal reconstruction of a smooth curve $C$ without boundary from a discrete set of sample points $S$. It is known that if $S$ is an a $\...
- 413
1
vote
1
answer
50
views
On triangulations and "coverage" of circumcircles
Let $P$ be a convex quadrilateral defined by four vertices $a$, $b$, $c$, and $d$. Suppose that the circumcircle of $\triangle abd$ contains $c$.* Let $D(\triangle abc)$ to denote the area enclosed by ...
- 173
15
votes
1
answer
612
views
Acute triangles in "obtuse" polygons?
Let $P$ be a convex polygon. Suppose every interior angle of $P$ is obtuse. Is it always the case that there exist three vertices $p, q, r$ of $P$ such that $\triangle pqr$ is acute?
I conjecture ...
- 173
8
votes
1
answer
227
views
Counting polygons in arrangements
For an arrangement of lines $\cal{A}$ in the plane, an
inducing polygon $P$ is a simple polygon satisfying:
(a) every edge $e$ of $P$ lies on some line $\ell$ of $\cal{A}$, and
(b) every line $\ell \...
- 150k
2
votes
0
answers
57
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 ...
- 2,961
2
votes
1
answer
420
views
Build reversed No-Fit-Polygon
I need some robust algorithm to optimally fit one non-convex polygon into another. The destination one can contain holes.
Recently I found scholarly articles on this subject:
One of them describes ...
5
votes
1
answer
230
views
Generalizations of the "Curious Tiger" Polygon
I actually don't know, whether the polygon I describe here already has name, but let me explain the problem, that is solved by the polygon, with a little story:
Imagine a flat terrain with bushes of ...
- 12.8k
4
votes
2
answers
787
views
Fitting one Polygon in another
I have two Polygons A and B and I want to find the position, rotation and scale of B, so it fits into A and has the maximum Area possible. Also both can be concave.
I did some research but couldn't ...
- 41
0
votes
1
answer
558
views
Detect perimetral edges of a polygon [closed]
I'm developing a building editor. Users can draw rooms by adding angles (vertices of the room) with a left click. Clicking on an existing angle closes the room and fills the floor by using the ...
4
votes
2
answers
385
views
Construct polygon/polyhedron containing all points not externally visible w.r.t given polygon/polyhedron?
Is there an algorithm to construct a polyhedron containing all points in space for which there exists no ray to infinite not intersecting a given polyhedron?
In 2D, we could consider polygons. For ...
- 723
8
votes
2
answers
337
views
Angle subtended by the shortest segment that bisects the area of a convex polygon
Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...
- 113
6
votes
1
answer
2k
views
Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?
Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
- 163
2
votes
1
answer
173
views
Calculating the "Belvedere Hull" of a Simple Planar Polygon
As an informal motivation the problem, imagine a tower with polygonal footprint, that is located in a beautiful landscape, the "Belvedere Hull" is then related to the directions, in which one would ...
- 12.8k
0
votes
2
answers
3k
views
Determine the boundary points of a set of points [closed]
I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$?
There are methods like convex hull, concave hull and $\...
- 17
1
vote
0
answers
65
views
Non-Convex Polygons with "Antipodal Visibility"
by "antipodal visibility" of planar, simple polygons I mean the following property:
if two points $p$ and $q$ on the polygon's boundary divide the polygon's boundary into two polylines of equal length,...
- 12.8k