===============================================================

                            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.

**********************************************************************