1. Method: Vertex Clustering
This is more or less a low-quality method, but depending on your mesh it could work well.
The basic idea is to partition the space into a regular grid, and then choose one representative for each cell that holds at least one vertex.
Then calculate the connectivity based on the connectivity of the original vertices.
In the image you see a basic 2D clustering. The unreduced mesh on the left, and the reduced on the right with the chosen representatives.
As you can see, just choosing an existing vertex as representative (by closest to mean, or closest to center, or any other idea you can think of) you get a subset of vertices.
But you also see the problem, thin parts will degenerate and parts that are close to forming a loop will probably get connected. But as already said, it depends on your mesh if this works.
2. Method: Incremental Mesh Decimation with with Half-edge Collapse
One vertex gets collapsed into its neighbour. Thereby you get again a subsampling.
This is a progressive method. You evaluate which collapse will decrease the quality (for example total distance to the original surface, but many more possible) and collapse it. Then you check if your quality has dropped too much for another collapse, and if so you stop. Otherwise you do it again. Until either the quality drops too much or the target size is reached.
Method 3: Progressive Mesh Decimation with Vertex Decimation.
The same progressive idea as in method 2, but this time instead of a collapse you just delete a vertex and calculate a new triangulation for the hole that this created.
