Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [polygons]

The tag has no usage guidance.

5
votes
1answer
171 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
92 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
60 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
148 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
160 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
126 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
181 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 ...
4
votes
2answers
732 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
234 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'...
39
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
86 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
110 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 ...
13
votes
1answer
578 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
268 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
487 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 ...
0
votes
1answer
395 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
578 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
266 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
90 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
153 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
294 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
543 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
811 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
440 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
289 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
419 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
270 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
197 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
655 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 ...
4
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
133 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
128 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
427 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
121 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
99 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
58 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
245 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
49 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
2k 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 ...
2
votes
1answer
241 views

What is the median area of a random n-gon inside a unit square?

A square is bounded by the coordinates (0,0), (0,1), (1,0) and (1,1). Random x and y coordinates are chosen in the interval [0,1] for each of the n points. The n points are then randomly connected to ...
3
votes
1answer
304 views

What is the shape of the convex $n$ -gon which gives the maximum of a function?

Supposing that the length of every edge of the convex $n$-gon $P_1P_2$$\cdots$$P_n$ is 1, what is the shape of the $n$-gon which gives the maximum of the following function $B_n$? $$B_n=\sum_{1\le{i}\...
9
votes
1answer
511 views

What is the shape of the $n$-gon which gives the maximum of a function?

What is the shape of the $n$-gon $P_1P_2\cdots P_n$ which gives the maximum of $A_n$? The quantity $A_n$ is defined by $$ A_n = \frac{{\sum_{i\lt{j}\le{n}}{\lvert P_i P_j\rvert}^2}-{\sum_{i=1}^{n}{\...
4
votes
1answer
1k views

Algorithms for covering a rectilinear polygon using the same multiple rectangles

Sorry for the crossing-posting: original post is here All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor ...
2
votes
1answer
340 views

Determining A valid Convex Hexagon given The length of Six sides

Suppose We are given the length of all six sides of a Convex Hexagon. How can we tell whether it's valid or Not ? that means can we tell whether it's area is positive or not ?
4
votes
4answers
17k views

How to find overlap between two convex hulls, along with the overlap area

I have two boundaries of two planar polygons, say, B1 and B2 of polygons P1 and P2 (with m and n points in Boundaries B1 and B2). I want to find out if the polygons overlap or not. If they overlap, ...
10
votes
1answer
6k views

Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon. In other words, I want to ...
6
votes
2answers
440 views

cyclic polygons & trigonometry

I posted this question to stackexchange, where it's generated some comments but no progress toward answering it. I'm going to say somewhat more here than I did there. At one vertex of a pentagon ...
6
votes
1answer
7k views

Determine if you can build a polygon from segments [closed]

Is there a way to determine whether it is possible to build a polygon from given n segments? Maybe triangle inequality generalized?