BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-96-1568
       ENTRY:: April 10, 1996
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Algorithms for computing intersection and union of toleranced
               polygons with applications
        TYPE:: Technical Report
      AUTHOR:: Cazals, Frederic
      AUTHOR:: Ramkumar, G. D. S.
        DATE:: April 1996
       PAGES:: 13
    ABSTRACT:: Since mechanical operations are performed only up to a
               certain precision, the geometry of parts involved in real
               life products is never known precisely. Nevertheless,
               operations on toleranced objects have not been studied
               extensively. In this paper, we initiate a study of the
               analysis of the union and intersection of toleranced simple
               polygons. We provide a practical and efficient algorithm that
               stores in an implicit data structure the information
               necessary to answer a request for specific values of the
               tolerances without performing a computation from scratch. If
               the polygons are of sizes m and n, and s is the number of
               intersections between edges occuring for all the combinations
               of tolerance values, the pre-processed data structure takes
               O(s) space and the algorithm that computes a
               union/intersection from it takes O((n+m) log(s) + k' + k
               log(k)) time where k is the number of vertices of the
               union/intersection and k <= k' <= s. Although the algorithm
               is not output sensitive, we show that the expectations of k
               and k' remain within a constant factor tau, a function of the
               input geometry. Finally, we list interesting applications of
               the algorithms related to feasibility of assembly and
               assembly sequencing of real assemblies.
       NOTES:: [Adminitrivia V1/Prg/19960410]
         END:: STAN//CS-TR-96-1568