0
votes
0answers
35 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...
0
votes
1answer
40 views

Cut the Cake into 4 parts

I'm facing the following problem: I'm given a set of coordinates on an integer grid that define the vertices of a polygon. The polygon is guaranteed to be convex. It's proven that such a polygon can ...
1
vote
1answer
26 views

What's wrong with this pseudocode for Forster-Overfelt's version of the Greiner-Horman polygon clipping algorithm?

The Problem I'm trying to understand and implement the Forster-Overfelt version of the Greiner-Horman polygon clipping algorithm. I've read the other Stackoverflow post about clarifying this ...
0
votes
3answers
53 views

Where is the interior of the polygon?

There is an axis-parallel (orthogonal) simply-connected polygon given as a list of corners. How can I know whether a certain vertical segment has the interior of the polygon on its east or on its ...
2
votes
2answers
128 views

What is inside and outside of complex polygon?

I am reading this paper http://arxiv.org/pdf/1207.3502.pdf Given a complex polygon. Its edges may intersect. The algorithm finds out if given point is inside of polygon or not. It draws a line from ...
0
votes
0answers
32 views

Is there a way to compute the empty area between a group of touching polygons?

Given a bunch of convex polygons layed out like a house truss, is there a way to compute the empty area, or get a polygon for each of those "holes" between the polygons? I tried starting from any ...
3
votes
0answers
84 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
1
vote
1answer
71 views

When is a convex polygon inscribable?

Defining the diameter of a convex polygon as the maximum possible distance between all pairs of vertices, can we conclude that the convex polygon is inscribable (i.e has all its sides as chords of a ...
8
votes
2answers
155 views

How to check if polylines can be untangled?

In a program I'm writing I need to be able to check whether a straight line between two points is homotopic to a polyline between them. For example in the below example the first one is equivalent to ...
1
vote
3answers
86 views

Are there any Heron-like formulas for convex polygons?

Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
1
vote
1answer
85 views

Diagonal of a convex polygon such that the obtained cuts have simmilar areas

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem Problem. Find in linear time a diagonal of $P$ such that the absolute ...
2
votes
1answer
818 views

How many rectangles can fit in a polygon with n-sides?

I am trying to write an algorithm to solve a problem I have. I have a few ideas of what the algorithm might be like but I am posting to see if anyone else has a better more efficient solution or any ...