Travel Maze problem (Intersecting Manifold Clustering)
Robust elastic principal graphs are able to deal with complex data distributions when other clustering or manifold learning algorithms would fail. One of such problems is solving the kid's travel maze problem in 2D, where non-linear trajectories can intersect at multiple points. More generally, this problem is related to intersecting manifold clustering [1].
Below you see an example of how ElPiGraph solves a travel maze problem by approximating each trajectory with a robust principal curve, each time starting from a position in the dataset where no previous trajectory has passed yet. In the end, the dataset is clustered into disjoint clusters of curvilinear shape having multiple small intersections.
This image is produced by the following script in ElPiGraph.M
setallpaths; testTravelMazeProblem;
In this example we assume the number of trajectories known (three). It is relatively simple to improve the script such that it will determine the number of trajectories automatically, by checking if the set of captured points is empty.