Questions tagged [polygons]
The polygons tag has no usage guidance.
70
questions
3
votes
0answers
154 views
Hypothesis: An injection from polygons into $SO(2) \times S_n$
I have stumbled upon a possible representation of polygons by a concise description of their behaviour under rotation. I would like to know more about it and, obviously, if it is actually a bijection. ...
9
votes
2answers
511 views
Strange formula for area of a convex polygon
Consider a convex $n-$gon in $\mathbb{R}^2$ with sides contained in the lines $y=k_ix+b_i, 1\leq i\leq n.$ Then its area equals to
$$
S=\frac{1}{2}\sum_{i=1}^{n} \frac{(b_{i+1}-b_i)^2}{k_{i+1}-k_i}.
$$...
0
votes
1answer
98 views
Point generation in polygon
I know about the Halton sequence. But so far I can’t find the formulas by which points are generated. Also worried is the question Halton sequence generates points only in the rectangle? Or can I ...
1
vote
1answer
73 views
Can we split a polygon in half (vertex-wise) by a diagonal, but with a constant maximum difference?
This is a followup to my last question - Can we prove that simple polygons can always be split in half (vertex-wise) by diagonals?
Is there a constant natural number K for which the following is true:...
0
votes
1answer
55 views
Can we prove that simple polygons can always be split in half (vertex-wise) by diagonals?
Can we prove that for any simple polygon with more than 3 vertices there always exists a diagonal which:
is inside the polygon
doesn't intersect with any edges
splits the polygon in two polygons in ...
0
votes
0answers
77 views
Automorphism group of the cycle graph with $k$ diagonals
Let $C_n$ be the cycle graph on $n$ vertices. Then $Aut(C_n) \cong D_{2n}$ the dihedral group of order $n$.
Now, let $C_{n,i}$ be the cycle graph with $i$ many diagonals connecting opposite vertices ...
2
votes
0answers
42 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
90 views
Projections of particular simplex yielding boundary of a regular polygon?
What is the maximum $m$ such that there is a simplex with $n$ vertex points in $n-1$ dimensions whose projection yields boundary of a regular $m$-gon on $2D$ plane?
2
votes
1answer
122 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
1answer
195 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 ...
1
vote
1answer
97 views
Chain rotation of a point
Let $n$ be a positive integer number and $P$ be a point in a plane. Let $A_1$, $A_2$, $\cdots$, $A_m$ be $m$ points in the plane, we take modulo $m$ for $A_j$ (it is mean $A_{m+i}=A_{i}$ for $i=1, 2, \...
3
votes
2answers
115 views
Complexity of 2D-Minkowski sum of non-convex polygons
I have read that the complexity of computing the Minkowski-Sum of $2$ non-convex polygons (through convex decomposition) is $O(m^2 n^2)$, where $m$ and $n$ is the number of vertices of each polygon. ...
1
vote
1answer
154 views
How many points appear in the plane when the chain of n-gons is close?
Let $A_{11}A_{12}\cdots A_{1n}$ be a regular $n$ polygon, we call $A_{11}A_{12}\cdots A_{1n}$ is the $1st-n-gons$. Now we construct the $2nd-n-gon$ based two condition as follows:
$2nd-n-gons$ is ...
2
votes
0answers
163 views
In arbitrary cyclic polygon then $\sum_{i<j} x_{ij}^\alpha \ge \sum_{i<j} y_{ij}^\alpha $
I am looking for a proof of the inequality as follows:
Conjecture: Let $A_1A_2....A_n$ be the regular polygon incribed a circle $(O)$. Let $B_1B_2....B_n$ be a polygon incribed the circle $(O)...
5
votes
2answers
158 views
An inequality related to area and sidelengths of a polygon $Area(A_1A_2…A_n) \le \frac{1}{n}cotg{\frac{\pi}{n}} \sum_{i=1}^nA_iA_{i+1}^2$
I am looking for a proof (or a reference) of an inequality related to a rea and the sidelengths of a polygon as follows:
Let $A_1A_2...A_n$ be arbitrary polygon, then:
$$Area(A_1A_2....A_n) \...
4
votes
2answers
288 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 ...
3
votes
2answers
833 views
What is the name of the 65537-gon? [closed]
I know the name of the heptadecagon (17 sides) and the diacosipentacontaheptagon (257 sides). But what is the name of the polygon with 65537 sides? I am unable to figure it.
4
votes
1answer
244 views
Reordering vertices of a polygon
Let $Q,Q'$ be two planar polygons with the same number $n>3$ of vertices. There is a correspondence between vertices of $Q$ and $Q'$: to any vertex $z$ of $Q$ corresponds a unique vertex $z'$ of $Q'...
40
votes
2answers
3k views
Can one “hear” the shape of a polygon via external reflections?
This question is a rough analog of Kac's "Can One Hear the Shape of a Drum?"
A closer analog is the recent "Bounce Theorem" that says, roughly, the shape of a polygon is determined by its billiard-...
1
vote
0answers
104 views
Is it possible to dissect a regular polygon into mirrored-symmetric pieces?
Q1. Planar regular triangle is dissected into three congruent pieces, each of them having no symmetry axis.
Can it be so, that one of these pieces is a mirrored (and then rotated) copy of some other ...
1
vote
0answers
123 views
Rectangular Newton polygon of a Jacobian pair
Let $p,q \in k[x,y]$, $k$ is a field of characteristic zero.
By definition, $p,q$ is a Jacobian pair if their Jacobian is invertible in $k[x,y]$, namely, $p_xq_y-p_yq_x \in k^*$, and $p,q$ is an ...
16
votes
2answers
792 views
Maximum area of the intersection of a parallelogram and a triangle
How large can the intersection of a parallelogram (or a square, if you prefer) with a triangle be, if each of them is of unit area? It is easy to see that the intersection can be of area 3/4 – is this ...
6
votes
2answers
273 views
Problem on distances in a polygon
In $\mathbb{R}^2$ consider a square (call it $S$) and three triangles (one acute $T_2$ and two obtuse $T_1$ and $T_3$) such that each triangle shares one different side with the square and the ...
4
votes
1answer
891 views
decompose rectilinear polygons into rectangles with minimum internal borders
I have a number of rectangles as shown in the attached diagram (labelled original) and I want to merge them together in a way (labelled Result ) to get the minimum internal borders. The reason I want ...
1
vote
1answer
568 views
Algo for covering maximum surface of a polygon with rectangles
I'm looking to an algorithm to covering maximum surface of a polygon with rectangles. Rectangles have to have a specific width, a rectangle can't overlap an other one and each one has to fit in the ...
7
votes
1answer
628 views
Three homothetic centers are collinear
I am looking a proof for the problem as follows:
Let a convex hexagon, such that its principal diagonals are concurrent. For each side of the hexagon, extend the adjacent sides to their ...
10
votes
0answers
306 views
Determining convexity of a polygon from its Fourier coefficients
Consider an $n$-sided polygonal curve in the plane, represented by an ordered set of points $(x_0, x_1, \ldots, x_{n-1})$; line segments connect consecutive points and also $x_{n-1}$ to $x_0$. It is ...
2
votes
1answer
97 views
Constructing a polygon of $n$ facets from a set of positive values representing the length of the facets [closed]
The input of my problem is a set of positive values $a=\{a_1,...,a_n\}$ where $n\geq 3$.
I want to construct an $n$-gon where the lengths of the $n$ facets are the values $a_i$ for $i=1,...,n$.
My ...
2
votes
1answer
175 views
Area of an irregular, n-sided, non-intersecting (edges) polygon algorithm
I need to generate an irregular, n-sided polygon of non-intersecting edges (n= 200, for example) with the smallest area possible. The position of the vertex is random and I've tried designing a couple ...
0
votes
0answers
302 views
Geodesic Digons in Reductive Spaces
Consider a naturally reductive homogeneous space $M$ of positive curvature. Is it necessarily the case that there exists a geodesic digon whose interior angles sum to less than $2\pi$? Angles are ...
12
votes
1answer
625 views
Limiting shape for Brillouin zones
Is it true that the limiting shape for Brillouin zones (for any lattice) is a circle?
You can find the definition and the step by step construction of Brillouin zones here. This picture is taken from ...
-7
votes
1answer
1k views
Gauss-Wantzel theorem, Fermat primes and solvability of S_n [closed]
Gauss-Wantzel theorem asserts that a polygon with $n$ sides is constructible if and only if $n$ is a product of a power of $2$ and distinct prime Fermat numbers, where the Fermat number of index $k$ ...
3
votes
4answers
467 views
Terminology for polygons
As you may know term "polygon" might mean few different things
and its meaning has to guessed from context.
By some reason I have to use few of these meaning in one place.
So I converge to the ...
0
votes
1answer
343 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
2answers
431 views
Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...
4
votes
2answers
303 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 ...
6
votes
1answer
213 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 ...
10
votes
3answers
737 views
Which polygons have *simple* periodic billiard paths?
I know (or, rather, believe) that it remains unknown whether every polygon
has a periodic billiard path.
But Howard Masur proved in the 1980's that every rational polygon
(vertex angles rational ...
5
votes
1answer
1k 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 ...
2
votes
1answer
142 views
Measuring the Randomness and Statistics of Convex Polygons
How can I tell, how likely it is, that a given convex polygon with a sufficiently high number of edges is random and, if so, what kind of randomness it is (e.g. white noise)?
What is known about ...
2
votes
1answer
146 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 ...
17
votes
1answer
457 views
Does the boundary of a convex body contain a regular planar pentagon?
How to prove or disprove that the boundary of any convex body in $\mathbb{R}^3$ includes 5 points which form a regular planar pentagon? The following consideration suggests the answer "yes": if we ...
8
votes
0answers
131 views
What does this number tell me about a convex lattice polygon?
EDIT: I realized I'd tricked myself by working with a too special case of $f$, the question is now updated (boundary lattice points replaced vertices).
Suppose I have a convex lattice polygon $P$, ...
0
votes
2answers
1k 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 $\...
1
vote
0answers
101 views
Intersection points of closed curves inscribed in a convex polygon
Suppose that I have two distinct simple closed curves, $C_1$ & $C_2$, and each is inscribed in a convex polygon, D. By inscribed, I mean tangent to each side of D. In particular, I am most ...
1
vote
0answers
60 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,...
37
votes
4answers
2k views
What polygons can be shrunk into themselves?
Let's call a polygon $P$ shrinkable if any down-scaled (dilated) version of $P$ can be translated into $P$. For example, the following triangle is shrinkable (the original polygon is green, the ...
4
votes
1answer
253 views
Most Regularity of a Polygon
Conseider $n$ electrons in an empty sphere. What structure do they make?
This question have two cases: (i) if electrons should be sit on the boundry of sphere (one can suppose that the boundry of ...
3
votes
0answers
51 views
Find shift direction for min overlap area of 2 polygons
I have 2 arbitrary polygons (concave or convex) with certain overlap.
Now there is some relative shift between these 2 polygons (vector s with a constant length).
I want to find the direction of s ...
6
votes
1answer
3k views
Shrink polygon to a specific area by offsetting
I have a 2D polygon that I want to shrink by a specific offset (A) to match a certain area ratio (R) of the original polygon. Is there a formula or algorithm for such a problem? I am interested in a ...
