P-simple points and parallel 3D skeletonization algorithms
Involved people : Gilles Bertrand, Laurent Perroton.
By definition, one can remove a simple point without
modifying the topology of an object. However the suppression in
parallel of simple points can change the topology of an object (fig.
5). In 2 dimensions, certain approaches were proposed to
solve this problem : one of the most popular consists in
classifying the points in four categories, the points of the northern
type, southern, eastern, or western. With each iteration, only the points
of a given type can be candidates for the suppression. However this
approach is not valid any more in a three-dimensional space, as
shown by the fig. 5: indeed, one must now consider the six
directions north, south, east, west, up, down, and items X and Y are
both of the "up" type.
Through the concept of P-simple point, we propose a
general strategy to remove points in parallel without changing the
topology. This concept of P-simple point corresponds to a concept of
strong homotopy: a set Y is strongly homotopic with a set X, if Y
is included in X and if for any Z, such as Y included in Z and Z
included in X, Z is homotopic with X. In this case P = X\Y consists of
points known as P-simple (see fig. 6).
We proposed a characterization of the P-simple points which
can be carried out in a linear time. The problem that we solved was a
priori exponential, this result is thus completely unexpected
[ Ber95b ,
Ber95c ].
Figure 5: An object made up of two parallelepipeds
``linked'' by two points X and Y : the points X and Y are both
simple there, however they cannot be removed in parallel without
changing topology.
 |
 |
| (A)
| (b)
|
Figure 6: The black discs represent the points of Y = X\P,
and the black squares represent the points of P. (A): The central
point is P-simple, (b): the central point X is not P-simple,
because by removing certain points of P, one can make X nonsimple.