=============================================================== COAP Software FORUM =============================================================== EXTERIOR RANDOM COVERING ALGORITHMS ----------------------------------- The enclosed software consists of four main programs: herc.c, hlrc.c, herc2p.c, hlrc2p.c and five auxiliary programs: gepual.c, permal.c, polge1t.c, tpogcv.c, topgcc.c Application 1. -------------- herc.c- It Computes the directed Hausdorff distance between a set S of points generated at random in a box in R3, and a nonconvex polyhedron K. It also gives the number of computed distances between point and polyhedron which have been necessary. It uses the "Exterior Random Covering (ERC)" algorithm [1]. herc.c- It Computes the directed Hausdorff distance between a set S of points generated at random in a box in R3, and a nonconvex polyhedron K. It also gives the number of computed distances between point and polyhedron which have been necessary. It uses the classical "Exterior Random Covering (LRC)" algorithm [1]. These two programs require the same data files 1) datpual-It contains the data of the set S (Coordinates of the points,...). This file is generated by the auxiliar program gepual.c. 2)datpol2- It contains the data of the nonconvex polyhedron K. We give this file in the case that K is composed by two boxes. (This is the more complex case studied in [1]). 3) datper- It contains a random permutation of 1,2,.....,number of points of S. This file is generated by the auxiliary program permal.c. Application 2 -------------- herc2p.c- It computes the Hausdorff distance between two convex polyhedra and the number of computed distances between point and polyhedron which have been necessary. It uses the "Exterior Random Covering (ERC)" algorithm [1]. hlrc2p.c- It computes the Hausdorff distance between two convex polyhedra and the number of computed distances between point and polyhedron which have been necessary. It uses the "Lipschitz Random Covering (ERC)" algorithm [1]. The four main programs have used the "Local Search Algorithm based on faces (LSABF)" for computing the projection of a point on a convex polyhedron [2]. herc2p.c and hlrc2p.c require 1) Four data files describing topology of each polyhedron. datcv->datcva (Polyhedron A),datcvb (Polyhedron B) datvc->datvca (Polyhedron A),datvcb (Polyhedron B) datcc->datcca (Polyhedron A),datccb (Polyhedron B) datvv->datvva (Polyhedron A),datvvb (Polyhedron B) 2)A file describing the metric data (Coordinates of the vertices) of each polyhedron datc->datca, datcb 3)A file containig a random permutation of the numbers 0,1,2,......., NVA(NVB)-1, where NVA(NVB) is the number of vertices of A(B) datper->datper1 (Polyhedron A), datper2 (Polyhedron B) These data files are generated by the auxiliary programs in the following way A) polge1t.c generates datc and datcv (we need execute this program for the polyhedron A and then for the polyhedron B). This program generates polyhedra inscribed on an ellipsoid. B) If we add the number of faces and vertices of the polyhedron considered, to the file datcv, we obtain the file datosr. Then a) From datosr topgcv.c generates the files datvc and datvv b) From datosr topgcc.c generates the file datcc. C) permal.c generates the file datper. (We have used different seeds for each polyhedron). We have included a more detailed information in the codes. ********************************************************************** References 1. B.Llanas. "Efficient Computation of the Hausdorff distance between Polytopes by Exterior Random Covering" (Submitted). Computational Optimization Appls. 2. B.Llanas,M.Fernandez de Sevilla and V.Feliu. "An iterative algorithm for finding a nearest pair of points in two convex subsets of RN" Comput. Math. Appl.,Vol 40, pp. 971-983, 2000. ********************************************************************** 