Suppose that I have a vector of points:
vector<int> points;
Triangles store the indices of points they are made of:
struct Triangle {
int p0, p1, p2;
};
Triangle tri0;
tri0.p0 = 3;
tri0.p1 = 6;
tri0.p2 = 7;
Triangle tri1;
tri1.p0 = 4;
tri1.p1 = 6;
tri1.p2 = 7;
Now I decide to erase point[3]. However, if I erase the point[3], the indices of points after index 3 will shift back so I need to notify all triangles that the indices they store might be changed. What could be a plausible way of notifying triangles?
It seems to me that the most plausible way is not to delete vertices. Because if you really delete them, then you have to shift all the vertices to the right (V/2 elements on average), then you have to go through all the triangles (T checks always).
Instead, you can mark vertices as dead. Simply put some bad value to points array (in you sample -1 is ok). Putting a mark takes only O(1) on each deletition. From time to time you might want to physically remove dead vertices. You can do it with two full passes (one over vertices, one over triangles), and compress your mesh in linear time O(V + T).
In order to make things easy to use, I suggest creating a class for your meshes. In a mesh object, maintain the number of dead entries transparently to class user. When portion of dead entries becomes considerable (e.g. more than half) after a deletition, call dead vertices elimination. You can also make triangle enumeration methods, which would iterate only over alive triangles (just for convenience).
This approach ensures O(1) amortized time per deletition, if amount of time spent in compression is no greater than number of deletitions multiplied by constant. Given that T <= c V at any moment (for some constant c), it is true. Indeed, it is very unlikely to see a mesh with number of triangles much greater than number of vertices, so you are fine.
A very different solution would be to use linked lists instead of arrays for storing vertices and triangles (with pointers to each other). In this case you can remove a vertex v in O(Sv) time, where Sv is number of triangles it belongs to. But low-level performance of such data structure may be poor.
EDIT: Another problem came into my mind. Dead vertices elimination is called transparently to user, but at the moment the user may be caught in the middle of triangles or vertices enumeration. Obviously this situation would cause great troubles.
In order to avoid the hazard, add lock/unlock methods to your mesh. Then you can ensure that as long as a mesh is locked, its vertices are guaranteed to stay in place index-wise. In such case you can safely perform operations like vertex filtering, for example.