New answers tagged

0 votes

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 ...
user avatar
  • 3,910
2 votes
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 ...
user avatar
  • 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 ...
user avatar
  • 2,977
4 votes
Accepted

The optimal complexity of intersecting a line with a convex hull of a set of points in 2d

What you're asking for reduces to finding the so-called bridges of the convex hull across this line, i.e. the two edges of the convex hull which have one vertex on both sides of the line. Kirkpatrick ...
user avatar
  • 2,209
0 votes

The optimal complexity of intersecting a line with a convex hull of a set of points in 2d

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(...
user avatar

Top 50 recent answers are included