I'm working on a project about sampling points, where the next point to be added to sample is the closest point to the current point. Furthermore, each point can only appear once in the sample.
Suppose we have 10 points (labeled 1-10) with coordinates $(x,y)$:
$$\{(4,0), (1,-4), (3,-4), (-2,4), (-1,-1), (2,3), (4,4), (-3,5), (3,2), (-2,0)\}$$
Then using a program like R, I can easily calculate the distance between pairs of points and list all the possible paths of a certain length (this length corresponds to the desired sample size). Note: When I use the term path, I am referring to a sequence of points, where the points are listed in the order in which they are selected. For example, if we set the sample size to 3, we obtain the following paths:
$$\{ {( 1, 2, 6), ( 1, 4, 9), ( 1, 10, 2), ( 2, 1, 4), ( 2, 1, 10), ( 2, 6, 8), ..., (10, 1, 2), (10, 1, 4)} \}$$
The triplet $(1,2,6)$ means that we first select point 1, then we move to point 2, then finally to point 6. In fact, point 1 has three nearest neighbours (points 2, 4, and 10) which is why we have three separate paths beginning with point 1, namely $(1,2,6), (1,4,9),$ and $(1,10,2)$.
Given a list of point coordinates and a fixed path length, I'm interested in determining the total number of possible paths and the number of paths that contain a particular point. In the example above, it turns out that there are 21 paths and 11 of those paths contain the point labeled 1.
I can get this information by enumerating all the paths, but this isn't practical when I have a large number of points.
Is there something in nearest neighbour theory that could help me compute (or at least approximate) the number of paths, and the number of paths that contain a particular point, given that I have point locations and a specified path length? I've never taken a course on graph theory so I'm not even sure where to look.
Any alternatives to my "brute force" approach would be much appreciated!
You have Hamiltonian path listed as a tag. A Hamiltonian path visits each vertex exactly once. The number of such paths is $n!$, assuming the points are just vertices in the graph sense and edges connect vertices. Each path contains each vertex.
I assume this is not what you are looking for, in which case I suggest making your problem well-defined and unambiguous.