computational geometry

*To*: mathgroup at yoda.physics.unc.edu*Subject*: computational geometry*From*: msdrl!nachbar at uunet.uu.net (Dr. Robert B. Nachbar)*Date*: Wed, 30 Dec 92 9:52:19 EDT

given a set of points in the plane, one can easily determine the minimum, maximum, and average distance from some position within their midst. now if these points are not infintesimally small (they are, foe example, circles with individual radii), what are the above measures from some position within their midst to the perimeters of the circles? the distances among the centers of the circles and their radii are such that a single envelope can be constructed from arcs of the "outermost" circles, that is, they are contiguous. i've tried a numerical approach by placing points on the circles and using ConvexHull from DiscreteMath`ComputationalGeometry`, but by definition it is wrong because the hull is not always convex (i.e., the invaginations are important to the application). besides, on my macintosh, it is slow. does anyone have a function that will find the "envelope" from such a set of points? as an extension, i would like to treat spheres (and more generally, elipsoids) in E^3 as well, again with but a single enveloping surface. exact solutions are welcome, as are numerical approximations. efficiency is important because i have several hundred sets of points to analyze. bob -- Dr. Robert B. Nachbar | Merck Research Laboratories | 908/594-7795 nachbar at msdrl.com | R50S-100 | 908/594-4224 FAX | PO Box 2000 | | Rahway, NJ 07065 |