5
votes
0answers
70 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
4
votes
2answers
108 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
1
vote
1answer
103 views

Graphics clipping: How can repeated half-space clipping fail?

Hi I am currently going through the past exam problems and I am stuck on this clipping problem. Could you give me some hint on how to solve it? If we clip a polygon to a window, it is inadequate ...
1
vote
2answers
129 views

Checking convexity from outside

Is there any method or algorithm to determine convex (or non-convexity) property of a region from outside (perimeter) ? One way is plotting tangent line in each point of perimeter and discuss how ...
1
vote
1answer
100 views

What is the typical method for sampling uniformly in a convex polytope

The polytope in my case is the intersection of the k-plane $Ax=b$ and $\{x>0\}$ where $A$ is the constraint matrix and $b$ is some solution. I'd like to find a method that is fast and efficient for ...
0
votes
2answers
190 views

distance between a polytope point and a polytope vertex

How to find distance in between any polytope point to the closest vertex of the polytope (the verteces of the polytope are known)? How to find a distance from the farest polytope point to the closest ...
4
votes
3answers
273 views

Average degree of convex hull vertices in a Delaunay triangulation

Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
1
vote
2answers
169 views

Find outline of $N$ points in a plane

If I have $N$ point coordinates $P_i = ( x_i, \, y_i ) $ and I want to draw the outline connecting only the points on the "outside", what is the algorithm to do this? This is what I want to do: ...
1
vote
1answer
103 views

Convex Hull in Hierarchy Structure

As a beggining to convex hull algorithms lecturer introduced the structure which it's called "Hierarchy Structure". Hierarchy Structure: in every given convex hull there is a maximum size convex hull ...
2
votes
1answer
96 views

Algorithm for Identifying Convex Kernel

What algorithms currently exist to determine the convex kernel of any low-dimensional set, especially a planar set? Also, if one exists, what research has been done on it and are there any references ...
2
votes
1answer
801 views

Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull