6
$\begingroup$

Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded in $\mathbb R^3$ ($n=3$) and one-dimensional chains of line segments ($k=1$) in $\mathbb R^n$.

Given many points $\{x_i\}_{i=1}^M\subset \mathbb R^n$, is there a data structure/algorithm for efficiently answering closest point queries of the form $\min_{y\in\mathcal S} \|x_i-y\|_2$?

I'm looking for a generalization of methods that handle, e.g., closest point on a triangle mesh. Pointers to existing implementations are also much appreciated!

$\endgroup$
2
  • $\begingroup$ The case for $k=1$ and $n=2$ can be solved efficiently with point location queries on a Voronoi diagram, see e.g. this question. This question on mathoverflow asks whether the Voronoi approach can be generalized to $k\leq 2$ and $n\leq 3$. And the answer is that this is very difficult to do exactly. $\endgroup$ – Discrete lizard Sep 30 '20 at 7:45
  • $\begingroup$ So even the example where you seem to suggest there are methods available seems difficult to handle exactly and efficiently. Could you list an example of method that works for a triangle mesh, so we can get a better idea what sort of solution you're looking for? $\endgroup$ – Discrete lizard Sep 30 '20 at 7:45
1
$\begingroup$

If you have only a single k-complex and you want to get the closest point regardless of whether it is a neighbor, then you can simply use any spatial index that supports nearest neighbor queries. For low dimensionality, such as 3 or 6, kd-trees, r-trees or some quadtrees (such as the PH-Tree) will work fine. In my experience, especially the R-Tree and PH-Tree work fine with millions of points.

C++ implementations are available from libSpatialIndex, Boost R-Tree, PH-Tree C++, and many others.

For Java implementations, have a look at my TinSpin Index Library or any other one.

Disclaimer: I am the developer of TinSpin and PH-Tree.

EDIT

I assumed by point you mean vertex, my mistake. I think you can adapt the approach if you are looking for nearest points on any simplex: Instead of storing vertices in the index, you can store the 2D/3D/$k$D bounding boxes of all geometries (vertices/lines/triangles/..) in the tree. Then there are two options:

  1. Use a nearest neighbor search to go through all bounding boxes and their elements to calculate the actual distance. You will have to check and compare these distances until the distance of the bounding boxes becomes larger than the current closest simplex you could find.
  2. Implement a custom distance function that returns nearest neighbors sorted by their closest point. This may require in depth knowledge of the index you are using.

This should still result in a $O(log(numberOfSimplexes))$ unless there are a lot of elongated geometries with overlapping bounding boxes. For example, a bad case would be a spherical data space with all geometries being lines that represent the diameter. By intuition, I think R-Trees or the PH-tree are best suited for this kind of search.

I have little experience with this, but for larger dimensionality $k$, the bounding box approach may work less well because boxes in $k$-dim space tend to become very large, so they may be a lot of overlap (or maybe not, because the whole dataspace is also growing exponentially?).

In any case, it can make sense to break up 'flat' objects (such as line segments in 3D) in to multiple segments in order to represent them with a chain of smaller bounding boxes instead of one large bounding box. Having several small bounding boxes if more efficient than one large one.

$\endgroup$
2
  • 1
    $\begingroup$ How does this approach handle the case when the nearest neighbor on the complex is not a vertex? Do these spatial indices easily support higher dimensional simplices by default? $\endgroup$ – Discrete lizard Sep 29 '20 at 21:05
  • $\begingroup$ I have the same question :-) $\endgroup$ – Justin Solomon Sep 29 '20 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.