8
votes
2answers
191 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 ...
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$. ...
3
votes
1answer
82 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 ...
2
votes
0answers
307 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 ...
4
votes
1answer
855 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 ...
3
votes
1answer
604 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 ...
4
votes
1answer
141 views

Shortest path in polygonal domain

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 ...
1
vote
1answer
579 views

Find out the border of a planar figure for given a set of points – 2D case

Original post is edited after getting some suggestions; I am looking for a fast algorithm which is able to detect outer most boundary of a plane for given set of points. Suppose, I have 3D point ...