Questions tagged [polygons]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...