Tessellations by connection

Michel Couprie

doi:10.1016/S0167-8655(01)00140-4

Tessellations by connection

2002-04-01

4

PRE

AI

DOI：10.1016/S0167-8655(01)00140-4

Original

Original request for help

Save

Abstract

En 中文

Let us consider a set R of points of the plane, composed of n connected components R-1,...,R-n. To each component R-i, we can associate the set V-t of points y of the plane that are strictly closer to R-i than to any other component of R. The set Vi is called the influence zone of R-i. It is a generalization of the well-known concept of the Voronoi region, The influence zones transformation is the map which associates, to each set R, the set V which is the union of the influence zones of the connected components of R. In the discrete space Z(2), with the distances d(4) and d(8), the influence zones transformation does not preserve any topological characteristic, not even the number of connected components. We propose a new approach based on the notion of order. An order is equivalent to a discrete topological space (in the sense of Alexandroff). In such a space, we introduce some transformations that preserve the connected components: the tessellations by connection. We prove that the influence zones transformation, defined thanks to the distance based on shortest paths, preserves the connected components of any closed set. We define, by the way of a parallel algorithm, a particular tessellation by connection which includes the influence zones and thus is centered. Furthermore, the centered tessellation by connection produces thinner frontiers than the influence zones transformation. (C) 2002 Elsevier Science B.V. All rights reserved.

Keywords:

discrete topology

order

discrete distance

Voronoi tessellation

skeleton

influence zones

Tessellations by connection

Abstract

AI Summary

Journal

Organization