From: Laurent Siebenmann <Laurent.Siebenmann@...>

Date: Sun, 30 May 1999 04:25:17 +0200 (MET DST)

Date: Sun, 30 May 1999 04:25:17 +0200 (MET DST)

[apologies if this is a repeat from about a week ago] Dear Robert Covington, > It would be nice to feed in a "point cloud" as it is > called in 3D vernacular in either 2D XY pts or 3D XYZ pts > and be able to have a routine that will mesh that into the > proper shape automatically. This is probably subject of a lot of programming technology, so regard my suggestion below as naive and uninformed. Consider a finite set of points in the plane (cloud). There is a very simple and natural algorithm that leads not to a triangulation with the given vertices but to a tiling of the plane with one convex polygonal tile containing each given point in its interior. The tile T for point P is the set of all points that are nearer to P than to any other point in the cloud. Each face of the tile T is a segment in the line of points that lie equidistant between P and some other point Q of the cloud, and that suggests the algorithm. From a tiling one can go on to a triangilation with some extra vertices but maybe the tiling is what you really need... T is called the Diriclet region of P for the given cloud of points. Or the Voronoi region. These ideas work in any dimension. Cheers Larry Siebenmann