I aim to choose a set of vertices on a 3D mesh in such a way they are not adjacent, I thought about using an algorithm of simplification but that will change the resolution of a mesh, thing I avoid to do. I don't know if the algorithms we apply on graphes would be helpful like ''Spanning tree of minimum weight'' or any other one. And other thing I avoid also to use the adjacency matrix because I have a high number of vertices.
.
your set must have another characteristic than just having non adjacent vertices ; maybe it should be as large as possible or something of this kind ?
anyway, what you are looking for is known as an "independent set" in graph theory :
https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29
.
Yo creo que se pueden escoger los vértices no adyacentes y crear un grupo específico donde los otros vertices del mesh quedan independientes del grupo.
Quizás puede utilizarse el software blender.
On a 3-D mesh, every vertex will have at most six neighbors. I imagine you could use an adjacency list as a database, it should be economic and easy to generate. You didn't specify how many vertices you want to pick up as an independent set, but it seems that you could make a random vertex selection within the mesh and mark the neighbors of each chosen vertex as values on the adjacency list. If for a new vertex you find any neighbor already marked, then it will be adjacent to a previously chosen vertex and should be rejected.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs