Questions tagged [polygons]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
107 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 ...
Alan Horwitz's user avatar
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,...
Manfred Weis's user avatar
  • 12.6k
37 votes
4 answers
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 ...
Erel Segal-Halevi's user avatar
4 votes
1 answer
271 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 ...
Arash Ahadi's user avatar
3 votes
0 answers
56 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 ...
Yenwen's user avatar
  • 31
7 votes
1 answer
5k 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 ...
timkado's user avatar
  • 171
2 votes
1 answer
293 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 ...
William's user avatar
  • 23
3 votes
1 answer
343 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}\...
mathlove's user avatar
  • 4,727
9 votes
1 answer
544 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}{\...
mathlove's user avatar
  • 4,727
4 votes
1 answer
2k 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 ...
Sean's user avatar
  • 143
2 votes
1 answer
468 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 ?
rock_lee's user avatar
5 votes
4 answers
23k 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, ...
Harsha's user avatar
  • 53
10 votes
1 answer
8k 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 ...
Josh C.'s user avatar
  • 325
7 votes
2 answers
572 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 ...
Michael Hardy's user avatar
8 votes
1 answer
8k 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?
michal's user avatar
  • 97
4 votes
1 answer
256 views

Polar interpretation of convexity

Let $C$ be a convex polygon in the plane containing the origin, and let $r(\theta)$ for $\theta\in[0,2\pi)$ be a parametrization of its boundary. Is there a condition on $r$ that is equivalent to (or ...
Jennifer Gao's user avatar
2 votes
5 answers
6k views

Quadrilateral from 4 random points

Given 4 random points in 2D, how do I compute the area of the quadrilateral formed by the points? I'm aware of formulae giving the area when I know the sides a,b,c,d and the diagonals p & q. But ...
roadrunner66's user avatar
20 votes
2 answers
24k views

Partitioning a polygon into convex parts

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible. I know almost nothing about this subject, so I've been searching on Google ...
user14059's user avatar
  • 201
9 votes
5 answers
13k views

Get a point inside a polygon

I have a 2D polygon of arbitrary geometry. I need to find any point that is inside of that polygon. Taking the center won't work, because the polygon might not be convex. Is there a way to quickly ...
user10306's user avatar
  • 201
6 votes
1 answer
756 views

Using mirrors to make a non-convex polygon visible from a fixed interior point

Take a point $A$ inside a non-convex polygon $P$. Is it always possible to place a finite set of mirrors given by straight segments (not necessarily along the boundary of $P$, any position inside $P$ ...
Roland Bacher's user avatar
3 votes
3 answers
2k views

Is there a simple criterion to determine if two parallelograms intersect?

Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty? Note that I do not need to actually find the intersection.
Philipp's user avatar
  • 969
6 votes
1 answer
708 views

Elementary problem about triangles inside a convex polygon

Let P be a convex polygon with area A(P), and to each side of P, attach the largest area triangle possible that lies entirely within P. Must the sum S(P) of the areas of these triangles always satisfy ...
Eric Tressler's user avatar
32 votes
5 answers
2k views

Nonconvex manhole covers

One common reason given for the circularity of manhole covers is that they can't fall through the manhole. For convex manhole covers, this property is equivalent to having constant width — if ...
Richard Dore's user avatar
  • 5,205
2 votes
4 answers
8k views

Compute the Centroid of a 3D Planar Polygon

Given a list of 3D coordinates that define the surface( Point3D1, Point3D2, Point3D3, and so ...
Graviton's user avatar
  • 381
11 votes
3 answers
20k views

Dividing a square into 5 equal squares

Can you divide one square paper into five equal squares? You have a scissor and glue. You can measure and cut and then attach as well. Only condition is You can't waste any paper.
sanz's user avatar
  • 303
5 votes
2 answers
452 views

Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
Andrew's user avatar
  • 341

1 2
3