Closest point in embedded simplicial complex

Question

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!

Answer 1

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.