# Tag Info

## New answers tagged computational-geometry

### Concentric convex hulls

Because of the rule "we move all these points to a visited set and continue", your problem is degenerate. Because the hull of a single point is the point itself, which you eliminate and ...
• 3,910
Accepted

### A nearest neighbor data structure for meshes

It suffices to store all of the triangles from all of the meshes in a nearest-neighbor data structure for triangles. Then, given a point P, find the nearest triangle, check which mesh that triangle ...
• 141k
1 vote
Accepted

### Delaunay triangulation from an EMST

The Wikipedia article states, that: the Delaunay triangulation can be constructed from the Euclidean minimum spanning tree in the near-linear time bound $O(n\log ^{*}n)$, where $\log ^{*}$ denotes ...
• 2,977
I think it can be done in O(N). WLOG, we assume the line is $x=0$, and the intersection set is non empty. We can rotate the point set if the line is not $x=0$. The intersection check can be done in O(...