# Tagged Questions

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 ...
208 views

### Visual illustrations of circle packing theorem?

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. Paper Collins, Stephenson: A circle ...
74 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$. ...
83 views

### Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...
314 views

### Algorithm for Collection of Shortest Paths in a Grid without any clash at a point of time.

The efficient algorithm needs to be done and proved for the best solution for the given problem: User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination ...
930 views

### Star-Shaped polygons

We call a polygon star-shaped if there exists at least one point for which the entire polygon is "visible" from that point. The set of such points we call the kernel of the polygon. The art-gallery ...
700 views

### Finding the virtual center of a cloud of points.

Given: (latitude, longitude) points $P_1, P_2,\ldots, P_n$. Presumably, all the points should form a dense cloud. However, noise is possible. Needed: The virtual center of the points. For ...
The single shot query for the shortest path between two points in a plane environment with polygonal obstacles of complexity $O(n)$ can be solved in time $O(n \log n)$ using the continuous Dijkstra ...