arXiv:0808.2931v1 [cs.CG] 21 Aug 2008  Spatial planning with constraints on translational distances between geometric objects   ∗  Gennady Pustylnik   †  November 16, 2018  Abstract  The main constraint on relative position of geometric objects, used in spatial planning for computing the C-space maps (for example, in robotics, CAD, and packaging), is the relative non-overlapping of objects. This is the simplest constraint in which the minimum translational distance between objects is greater than zero, or more generally, than some positive value. We present a technique, based on the Minkowski operations, for generating the translational C-space maps for spatial planning with more general and more complex constraints on the relative position of geometric objects, such as constraints on various types (not only on the minimum) of the translational distances between objects. The developed technique can also be used, respectively, for spatial planning with constraints on transla- tional distances in a given direction, and rotational distances between geometric objects, as well as for spatial planning with given dynamic geometric situation of moving objects.  Keywords:   Spatial planning, Configuration space, Minkowski operations.  1 Introduction  Problems concerning the relative placement of geometric objects are called   spatial planning  problems [29]. Such problems are important in robotics [24], collision detection [21], [27], and computer-aided design and manufacturing (CAD/CAM) [11], [54]. A technique commonly used for solving spatial planning problems is the   configuration space   (or   C-space ) approach, based on representing each placement of an object, i.e., its posi- tion and orientation, as a point in some parametric C-space [28], [29]. (Each coordinate of the C-space represents a degree of freedom in the position or orientation of the object.) Given a collection of objects, the   translational   spatial planning problem consists in comput- ing the set of all the feasible positions (the orientations are fixed) of the objects, where certain constraints on their relative position are specified. The feasible region of (placements of) an object is called the   free   C-space of the object. The prohibited configurations of an object form a   forbidden   region. The   C-space mapping   for a particular spatial planning problem consists in partitioning the C-space into free and forbidden regions, where the latter are called   C-space obstacles . See [29] and [63] for more details.  ∗ A full version of this paper is available at [42].  † PG–Consulting,   Holon   58371,   Israel.   Email   addreses:   genap@post.tau.ac.il ,  gennadypus@walla.com .  1
1.1 Previous and related work  Detailed surveys of previous work on spatial planning can be found in [9], [14], [21], [27], [29], and [63]. See also [2], [4], [26], [33], [54], and [58] and references therein for other related works on placement and spatial planning. The basic constraint on the relative position of geometric objects, used in spatial planning for generating the C-space maps, is the relative non-overlapping of objects; here the minimum translational distance between the objects must be greater than zero, or more generally, than some positive value. Indeed, this is a key requirement in robotics, packaging, and nesting. See, e.g., [4], [26], [27], [53], and [63].   However, the geometric problems arising in design and manufacturing require a placement of objects with more complex constraints on their relative position, such as constraints on the minimum and/or maximum translational distances between objects, and/or their Hausdorff distances.   The problem of generating the C-maps with such complex constraints is also interesting theoretically. Placement problems taking into account the minimum translational distance (MTD) be- tween objects arise in industrial applications, concerning the cutting of materials, the layout of templates on a stock material, and the layout of an IC chip with geometric design constraints. See, e.g., [9], [29], [33], [53], and [54]. In these problems the MTD has to be at least the cutting tolerance of the machine that cuts the shapes out of stock material, or the minimal feasible dis- tances between electronic modules of an IC chip. Placement problems with constraints on the MTD between objects have been formulated in [53] and [54]. The papers [37] and [54] have considered placement problems with consrtaints on the minimal value of MTD between objects, and placement problems with constraints on both the minimal and maximal admissible values of MTD have been considered in [54]. Algorithms for solving various placement problems with constraints on the MTD have been considered in [37], [54], and [56] – [58]. The work in [39] has solved the problem of placement of a pair of objects with constraints on the   minimum   and   maximum   translational distances between them, and has also considered distances involving containment of objects.   Placement problems with constraints on several types of   translational   distances between objects, including directional Hausdorff distances be- tween objects, have been studied in [40] and [41]. These works have also studied a Boolean function, called the   geometric situation , which describes the system of constraints on the rela- tive position of objects, and have formulated and solved placement problems with several other types of geometric situations, namely, with rotational and dynamic geometric situations. An algorithm for computing the minimum Hausdorff distance between two planar objects under translation is given in [1]. (Efficient computation of Hausdorff distances has applications, e.g., in pattern recognition and computer vision; see [1] and [49].) This work has also studied placement problems taking into account bidirectional Hausdorff distances between objects. This paper presents a technique, based on the Minkowski operations, for generating the translational C-space maps for spatial planning problems with more general and more complex constraints on the relative position of geometric objects. This technique is an extention of that reported in [40] and [41]. The developed technique can also be used, respectively, for spatial planning with constraints on   translational distances in a given direction , and/or on   rotational  distances between geometric objects, as well as for spatial planning with given   dynamic   geo- metric situation of moving objects. A full version of this paper is available at [42]. To formulate the problem let us first present the needed notations and definitions, and then consider the various standard distances between geometric objects.   We assume that the ge- 2
ometric objects are   regular   sets ( r -sets) in the Euclidean space   R n , for   n   =   2   or   3 , i.e., bounded, closed, and semi-analytic subsets of   R n   [43].   This means that, for any   r -set   A   of  R n ,   A   =   ki ( A ) , where   i   and   k   denote the   interior   and the   closure   of sets, respectively [43]. The   complement   and the   boundary   of   A   are denoted by   A c   and   ∂A , respectively, and a copy of   A   translated by a point (or a vector)   p   is denoted by   A   +   p . We denote by   A θ   a copy of   A  rotated by an angle   θ   about the origin   O   [24]. The   regularized   set operations on two objects   A  and   B   in   R n   are defined as   A   ⊗ ∗   B   =   ki ( A   ⊗   B ) , where   ⊗ ∈ {∪ ,   ∩ ,   \} ; see [43] and [44] for details. The   regularized   complement   A c ∗  of   A   is defined as   A c ∗  =   ki ( A c ) . The   r -sets are not algebraically closed under the standard set operations, but they are closed under the regularized set operations [43]. For example, the standard intersection   A   ∩   B   of   r -sets   A   and   B   needs not be regular, since its boundary may have   dangling   faces/edges and/or   isolated   points, but   A   ∩ ∗   B  is an   r -set.  1.2 Standard distances between geometric objects  Let us consider the following distances between objects   A   and   B   (see [1], [19], and [27]):  d 1 ( B, A ) = inf  a ∈ A   inf  b ∈ B   ‖ a   −   b ‖ ;   d 2 ( B, A ) = sup  a ∈ A  sup  b ∈ B  ‖ a   −   b ‖ ;  h ( A, B ) = sup  a ∈ A  inf  b ∈ B   ‖ a   −   b ‖ ;   h ( B, A ) = sup  b ∈ B  inf  a ∈ A   ‖ a   −   b ‖ ;  d ∗ ( A, B ) =   inf  a ∗ ∈ A c   inf  b ∈ B   ‖ a ∗   −   b ‖ ;   H ( A, B ) = max { h ( A, B ) , h ( B, A ) } ,  where   ‖·‖   is the Euclidean norm. The distance   h ( A, B )   is called the   directed   Hausdorff distance from   A   to   B , and the distance   H ( A, B )   is called the Hausdorff distance between   A   and   B , respectively; see [1].   H ( A, B )   is a metric on   R n . These distances between   r -sets have the following basic properties [19]:  d 1 ( A, B )   >   0   ⇐⇒   A   ∩   B   =   ∅ ;   d 2 ( A, A ) =   diam ( A );   H ( A, B ) = 0   ⇐⇒   A   =   B.  Clearly,   d ∗ ( A, B ) =   d 1 ( A c , B ) . Then we have   d ∗ ( A, B )   >   0   ⇐⇒   B ⊂ A .  1.3 Problem formulation  Let   A   be an unmovable object, and let   B   be another object, allowed only to translate. Let us consider the following problem:  Problem I   For given   λ 1 , . . . , λ 6 , and the corresponding constraint  ν I   ( B   +   p, A ) =  {[ d 1 ( B   +   p, A )   ≤   λ 1  ]   ⊙ 1  [ d 1 ( B   +   p, A )   ≥   λ 2  ]}  ⊙ 2  {[ d 2 ( B   +   p, A )   ≤   λ 3  ]   ⊙ 1  [ d 2 ( B   +   p, A )   ≥   λ 4  ]}  ⊙ 2  {[ d ∗ ( B   +   p, A )   ≤   λ 5  ]   ⊙ 1  [ d ∗ ( B   +   p, A )   ≥   λ 6  ]}  ,  where   ⊙ 1(2)   ∈ {∨ ,   ∧} , find the region   N I   ( B, A )   of all the feasible translations   B   +   p   of   B , in which   ν I   ( B   +   p, A )   holds. Thus, our goal is to find all the feasible positions   p   of   B   with respect to   A , under the above constraint on their relative position. This problem is generalization of the well known   Findspace  problem, formulated in [29]. If we let   p   =   O , then the function   ν I   ( B, A )   can be interpreted as the generalized Boolean   distance query ; see [27] for detailes. 3
2 Preliminaries  2.1 Minkowski operations  The   Minkowski sum , and the   Minkowski diffference   of objects   A   and   B   are defined as  A ⊕ B   =   { a   +   b   |   a   ∈   A, b   ∈   B }   =   ⋃  b ∈ B  ( A   +   b ) ,   and   A ⊖ B   =   ⋂  b ∈ B  ( A   +   b ) = ( A c ⊕ B ) c ,  respectively [30], [49]. See Figure 1(a). The Minkowski subtraction is a   dual   operation of the Minkowski addition. Note that   A ⊕ B   = ( A c ⊖ B ) c .  (b) (a)  O   x x O   B   ˇ B p 1  B   +   p 3  y   y  A   ⊖   ˇ B p 3  A   ⊖   B B   +   p 1  A ⊕   ˇ B A A ⊕ B A p 2  B   +   p 2  Figure 1: (a) The Minkowski sum   A ⊕ B , and the Minkowski difference   A   ⊖   B   of objects   A   and  B . (b) The objects   A ⊕   ˇ B , and   A   ⊖   ˇ B . Here   p 1   ∈   ∂ ( A ⊕   ˇ B ) ,   p 2   ∈   ∂ ( i A ⊕ i   ˇ B ) ,   ( B   +   p 1 , 2 )  ̇ ∩ A , and   p 3   ∈   ∂ ( A   ⊖   ˇ B ) ,   ( B   +   p 3 )  ̇ ⊂ A , respectively. (Dashed lines show an objects   B   +   p , where (a)   p   ∈   ∂A , (b)   p   ∈   ∂ ( i A ⊕ i   ˇ B )   (resp.,   p   ∈   ∂ ( A   ⊖   ˇ B ) ). Dotted lines show pieces of   ∂ ( i A ⊕ i B )  (resp.,   ∂ ( i A ⊕ i   ˇ B ) ).) Let   ˇ B   be the   reflection   of   B   with respect to the origin   O , i.e.,   ˇ B   =   {− b   |   b   ∈   B } . (For notational convenience, the object   ˇ B   is sometimes denoted by   − B .) Then the   dilation , and the  erosion   of   A   by   B   are defined as  A ⊕   ˇ B   =   { a   −   b   |   a   ∈   A, b   ∈   B }   =   ⋃  b ∈ B  ( A   −   b ) ,   and   A ⊖   ˇ B   =   ⋂  b ∈ B  ( A   −   b ) = ( A c ⊕   ˇ B ) c ,  respectively. See Figure 1(b). Many properties of the Minkowski operations are well known and well studied. See, e.g., [3], [14], [19], [26], [30], [31], and [49] for details. In this section we consider the properties of the Minkowski operations that we need for our purpose. In [8] and [14] it is shown that if an object   A   is a convex then   A ⊖ B   =   A ⊖ CH ( B ) =  A ⊖ ext ( B ) , where   CH ( B )   denote the   convex hull   of   B , and   ext ( B )   denote the set of   extreme points   of   B , i.e., the set of vertices of   CH ( B ) . In [31] it is shown that the Minkowski sum   A ⊕ B  4
of two   r -sets   A   and   B   always results in an   r -set, whereas the Minkowski difference   A ⊖ B   could be a non-regular set; see Figure 1(a). Since   A ⊕ ( − ( B   +   p )) = ( A ⊕   ˇ B )   −   p , we have (see, e.g., [3], [17], [29], [30], [38], and [55]):  ( B   +   p )   ∩   A   6   =   ∅   ⇐⇒   p   ∈   A ⊕   ˇ B ; ( B   +   p )   ∩   A   =   ∅   ⇐⇒   p   ∈   ( A ⊕   ˇ B ) c ; ( B   +   p )  ̇ ∩ A   ⇐⇒   p   ∈   ∂ ( i A ⊕ i   ˇ B ) ,  (1) where   B    ̇ ∩ A   = [( i A   ∩   i B   =   ∅ )   ∧   ( ∂A   ∩   ∂B   6   =   ∅ )]   denotes the   outer touching   of the objects  A   and   B . The object   A ⊕   ˇ B   is also called the   C-space obstacle   of   B   relative to   A   [29]. The set  ∂ ( i A ⊕ i   ˇ B )   has been introduced in [3], where it is referred to as the   outer envelope   of   A   and   ˇ B . In [3] it is shown that   ∂ ( A ⊕   ˇ B ) ⊆ ∂ ( i A ⊕ i   ˇ B ) , and that the set   ∂ ( i A ⊕ i   ˇ B )   may have coincident faces/edges and/or isolated vertices, which are   removed   from the open point set   i ( A ⊕   ˇ B ) ; see Figure 1. From the relationships   ∂ ( A ⊖   ˇ B ) =   ∂ ( A c ⊕ i   ˇ B )   and   A ⊖ ( − ( B   +   p )) = ( A ⊖   ˇ B )   −   p , it follows that if   A ⊖   ˇ B   6   =   ∅ , we get (see [30] and [39]):  ( B   +   p ) ⊂ A   ⇐⇒   p   ∈   A ⊖   ˇ B ; ( B   +   p )   6   ⊂   A   ⇐⇒   p   ∈   ( A ⊖   ˇ B ) c ; ( B   +   p )  ̇ ⊂ A   ⇐⇒   p   ∈   ∂ ( A ⊖   ˇ B ) ,  (2) where   B    ̇ ⊂ A   = [( A c   ∩   i B   =   ∅ )   ∧   ( ∂A   ∩   ∂B   6   =   ∅ )]   denotes the   inner touching   of   A   and   B . See Figure 1(b). By observations of [3] and [31] we have   ( i A ⊕ i B ) ⊆ i ( A ⊕ B ) ;   ( i A ⊖ i B ) ⊇ i ( A ⊖ B )   and  ∂ ( A ⊕ B ) ⊆ ∂ ( i A ⊕ i B );   ∂ ( A ⊖ B ) =   ∂ ( i A ⊖ i B ) =   ∂ ( A c ⊕ i B );  A ⊕ B   = ( i A ⊕ i B )   ∪   ∂ ( i A ⊕ i B );   A ⊖ B   =   i ( A ⊖ B )   ∪   ∂ ( A ⊖ B );   (3)  ( A ⊕ B ) c   = ( i A ⊕ i B ) c \ ∂ ( i A ⊕ i B );   ( A ⊖ B ) c   =   k [( A ⊖ B ) c ] \ ∂ ( A ⊖ B ) .   (4) From the observations of [19] it follows that, for   r -sets, we have  A ⊕ i B   =   i A ⊕ B   =   i A ⊕ i B ;   A ⊕ B   =   k ( i A ⊕ i B );   A ⊖ B   =   A ⊖ i B   =   i A ⊖ i B.   (5) (Clearly, for non-regular point sets, the above equalities do not necessarily hold.) Let us consider the difference   ˇ B ⊖ A .   From the properties of the Minkowski difference (see [30]) it follows that   p   ∈   ˇ B ⊖ A   if and only if   p / ∈   A ⊕   ˇ B c , and then   A   ∩   ( B c   +   p ) =   ∅ , i.e.,  A ⊂ ( B   +   p ) . Thus,   B   +   p   covers   A   if and only if   p   ∈   ˇ B ⊖ A . In other words,  A ⊂ ( B   +   p )   ⇐⇒   p   ∈   ˇ B ⊖ A ;  A   6   ⊂   ( B   +   p )   ⇐⇒   p   ∈   ( ˇ B ⊖ A ) c ;  A    ̇ ⊂ ( B   +   p )   ⇐⇒   p   ∈   ∂ ( ˇ B ⊖ A ) .  (6) (Note that, by previous observations,   ˇ B ⊖ A , in general, is a non-regular set.) In case where both   A   and   B   are allowed to translate, we have   ( A   ±   q ) ⊕ ( − ( B   ±   p )) = ( A ⊕   ˇ B )   ∓   p   ±   q ,   ( A   ±   q ) ⊖ ( − ( B   ±   p )) = ( A ⊖   ˇ B )   ∓   p   ±   q , and   ( − ( B   ±   p )) ⊖ ( A   ±   q ) = ( ˇ B ⊖ A )   ∓   p   ±   q , respectively. Then all the relationships of (1), (2), and (6) can be reformulated to handle this more general form. For instance,   ( B   +   p ) ⊂ ( A   +   q )   ⇐⇒   ( p   −   q )   ∈   A ⊖   ˇ B . (For 5
A ⊕   ˇ B   this well known fact (see, e.g., [17] and [49]) has widely been used in [2], [9], and [33], for solving various containment problems.) Clearly, for   p   =   O , we have  B   ∩   A   6   =   ∅   ⇐⇒   O   ∈   A ⊕   ˇ B ;  B ⊂ A   ⇐⇒   O   ∈   A ⊖   ˇ B ;  A ⊂ B   ⇐⇒   O   ∈   ˇ B ⊖ A,  which are alternative formulations of the   overlapping   of the objects   A   and   B , of the   containment  of   B   in   A , and of the   covering   of   A   by   B , respectively.  2.2 Distances between geometric objects concerning their outer relative position  The standard minimum distance   d 1 ( B, A )   does not take into account the “amount” of intersec- tion between objects   A   and   B , since   d 1 ( B, A ) = 0 , for   A   ∩   B   6   =   ∅ , regardless of how much they overlap. Minimum translational distance constraints that take into account penetration be- tween objects have been proposed in [5], [7], [35], [37], and [54]. The work in [42] consider one specific set of definitions of such minimum distances, since it has been defined in different ways. In this section we consider the translational distances, as defined in [7] and [37]. The   minimum translational   distance   MT D ( A, B ) , introduced in [7], is defined as  MT D ( A, B ) =  {   − MT D + ( A, B ) ,   for   A   ∩   B   6   =   ∅ ;  MT D + ( A, B ) ,   otherwise ,  where   MT D + ( A, B ) = inf {‖ t ‖ |   A    ̇ ∩ ( B   +   t ) } . The distances   γ 1 , 2 ( B, A )   between   A   and   B , suggested in [37], are defined as  γ 1 ( B, A ) =      inf c ∈ ∂ ( A ⊕   ˇ B )   ‖ c ‖ ,   for   A   ∩   B   =   ∅ ; 0 ,   for   A    ̇ ∩ B ;  −   inf c ∈ ∂ ( A ⊕   ˇ B )   ‖ c ‖ ,   for   A   ∩   B   6   =   ∅ , γ 2 ( B, A ) =   sup  c ∈ ∂ ( A ⊕   ˇ B )  ‖ c ‖ .  See Figure 2. The distance   γ 1 ( B, A )   is defined by the above relationship only in case where  ∂ ( A ⊕   ˇ B ) =   ∂ ( i A ⊕ i   ˇ B )   (see subsection 2.1). Then, in general, we obtain that  γ 1 ( B, A ) =  {   inf c ∈ ∂ ( i A ⊕ i   ˇ B )   ‖ c ‖ ,   for   A   ∩   B   =   ∅ ;  −   inf c ∈ ∂ ( i A ⊕ i   ˇ B )   ‖ c ‖ ,   otherwise .  See Figure 3. By the observations of subsection 2.1, we get   γ 1 ( B, A ) =   γ 1 ( O,   i A ⊕ i   ˇ B ) , and  γ 1 ( B, A )      <   0 ,   for   O   ∈   i A ⊕ i   ˇ B ; = 0 ,   for   O   ∈   ∂ ( i A ⊕ i   ˇ B );  >   0 ,   for   O   ∈   ( A ⊕   ˇ B ) c .  Note that in the above relationships the set   i A   (resp.,   i   ˇ B ) can be replaced by   A   (resp.,   ˇ B ), since  i A ⊕ i   ˇ B   =   A ⊕ i   ˇ B   =   i A ⊕   ˇ B , for   r -sets. See [42] for more details. It can easily be shown that   γ 1 ( B, A ) =   MT D ( A, B ) . Therefore we denote the minimum translational distance between   A   and   B   by   γ 1 ( B, A ) . 6
(a)   (b)   (c)  x y x y x y  γ 1 ( O, A ⊕   ˇ B )  A B A B A B γ 2   ( O, A ⊕   ˇ B )   γ 1 ( O, A ⊕   ˇ B )  O   O γ 2 ( B, A )   γ 1 ( B, A )   >   0  A ⊕   ˇ B   A ⊕   ˇ B   A ⊕   ˇ B O γ 1   ( B, A )   <   0  γ 1 ( B, A ) = 0  Figure 2: The distances   γ 1 , 2 ( B, A ) , for various relative positions of   A   and   B , in case where  ∂ ( A ⊕   ˇ B ) =   ∂ ( i A ⊕ i   ˇ B ) . Here (a)   A   ∩   B   6   =   ∅ , (b)   A    ̇ ∩ B , and (c)   A   ∩   B   =   ∅ , respectively.  (a)   (b)   (c)  x y x y  O γ 1   ( B, A ) = 0  O p y y  p x  A A B A B B γ 1   ( O,   i A ⊕ i   ˇ B )  ∂ ( i A ⊕ i   ˇ B )  ∂ ( i A ⊕ i   ˇ B )   ∂ ( i A ⊕ i   ˇ B )  O   γ 1   ( O,   i A ⊕ i   ˇ B )   x  γ 1   ( B, A )   >   0  Figure 3: The distance   γ 1 ( B, A ) , for various relative positions of   A   and   B , in case where  ∂ ( A ⊕   ˇ B ) ⊂ ∂ ( i A ⊕ i   ˇ B ) . Here (a)   A   ∩   B   6   =   ∅ ;   p x ,   p y   are the values of minimal translations of   B  in directions   x   and   y , corresponding to   γ 1 ( B, A ) , (b)   A    ̇ ∩ B , and (c)   A   ∩   B   =   ∅ , respectively. The properties of translational distances have been well studied. (See, e.g., [7], [17], [22], [34], [35], [37], [39], [54], and [56]. See also [42] for basic properties of   γ 1 , 2 ( B, A ) .) In [7], [17], [37], and [56] it is shown that   γ 1 ( B, A )   (resp.,   γ 2 ( B, A ) ) corresponds to the minimal (resp., maximal) translation   B   +   p   of   B   relative to   A   that reaches an outer touching   ( B   +   p )  ̇ ∩ A , and that   γ 1 ( B, A ) =   d 1 ( B, A ) , for   A   ∩   B   =   ∅ , and   γ 2 ( B, A ) =   γ 2 ( O, A ⊕   ˇ B ) =   d 2 ( B, A ) . The distances   γ 1 , 2 ( B, A )   are invariant with respect to both rotations and translations, i.e.,   γ 1 , 2 ( B θ   +  p, A θ   +   p ) =   γ 1 , 2 ( B, A ) ; see [35], [39], [56], and [57]. The papers [37] and [56] have considered the family of surfaces   ∂ ( A ⊕   ˇ B ⊕ λK ) , for   λ   ≥   0 , where   λK   is the ball of radius   λ   centered at   O . In these works it is shown that   γ 1 ( B   + p, A ) =   λ , for   p   ∈   ∂ ( A ⊕   ˇ B ⊕ λK ) .   The surfaces   ∂ ( A ⊕   ˇ B ⊖| λ | K ) , with similar properties, for negative values of   λ , have been defined in [56].   (Note that the above relationship holds only in case where   ∂ ( A ⊕   ˇ B ⊕ λK ) =   ∂ ( i A ⊕ i   ˇ B ⊕ i λK ) , for   λ >   0 , and   ∂ ( A ⊕   ˇ B ) =   ∂ ( i A ⊕ i   ˇ B ) , otherwise.) 7
3 Parametric families of a single object and distances between a point and an object  The parametric family of objects  Γ 1 ( λ, K, A ) =  {   A ⊕ λK,   for   λ   ≥   0;  A ⊖| λ | K,   for   −   r A   ≤   λ   ≤   0 ,  where   r A   is the radius of the largest inscribed ball in   A , is called the   full parallel pencil   of the object   A   [19], or, for   λ   ≥   0 , the   offsets   of   A   [47]. See Figure 4(a). The object   Γ 1 ( − r A , K, A )   is the locus of the centers of all largest inscribed balls in   A , and, in general, is a (curved) face/edge. Clearly,   Γ 1 ( − r A , K, A ) ⊂ A . A second parametric family of objects  Γ 2 ( λ, K, A ) =   λK ⊖ A,   for   λ   ≥   R A ,  where   R A   is the radius of the smallest circumscribed ball of   A , has been introduced in [40] and [41].   See Figure 4(b).   From the definition of Minkowski operations, it follows that  Γ 1 ( λ, K, A ) =   ∅   if and only if   λ <   − r A , and   Γ 2 ( λ, K, A ) =   ∅   if and only if   λ < R A . Since  λK   is convex, it follows that   Γ 2 ( λ, K, A )   is convex, for any bounded   A , and   Γ 2 ( λ, K, A ) = Γ 2 [ λ, K, CH ( A )] = Γ 2 [ λ, K, ext ( A )] ; see subsection 2.1. The object   Γ 2 ( R A , K, A )   is a single- ton point, which is the center of the (unique) smallest enclosing ball of   A . In general, the point of   Γ 2 ( R A , K, A )   needs not be in   A ; see Figure 4(b). From the definitions of   Γ 1 ( λ, K, A )   and  Γ 2 ( λ, K, A )   it follows that   Γ 2 ( λ, K, A ) ⊆ Γ 1 ( λ, K, A ) , for   λ   ≥   R A . (An equality holds in case where   A   is a singleton point.)  (b) (a)  y  λK O  y  O x   x  p γ 1   ( p, A )  p A γ 2 ( p, A ) Γ 1   ( λ, K, A )  A λ   =   R A  Γ 2   ( λ, K, A )  λ   =   − r A  Figure 4: The parametric families of objects   Γ 1 , 2 ( λ, K, A ) , for various values of   λ , and the distances   γ 1 , 2 ( p, A ) .   Here   Γ 2 ( R A , K, A )   6   ∈   A , dashed curves show   ∂ Γ 1 , 2 ( λ, K, A ) , and the dotted line shows a piece of   ∂ Γ 1 ( λ, K,   i A ) .   The objects   Γ 1 ( − r A , K, A )   and   Γ 2 ( R A , K, A )  consist of two singleton points, and a singleton point, respectively. 8
Let us consider the translational distances   γ 1 , 2 ( p, A )   between a point   p   and an object   A :  γ 1 ( p, A ) =      inf a ∈ ∂A   ‖ p   −   a ‖ ,   for   p   ∈   A c ; 0 ,   for   p   ∈   ∂A ;  −   inf a ∈ ∂A   ‖ p   −   a ‖ ,   for   p   ∈   i A, γ 2 ( p, A ) =   sup  a ∈ ∂A  ‖ p   −   a ‖ .  To lack of space, all proofs here and in the following sections are omitted. The proofs of the observations, lemmas, and theorems are presented in [42]. The distances   γ 1 , 2 ( p, A )   have the following properties:  Observation 1   (a) For   λ   ≥   0   we have  γ 1 ( p, A )      < λ,   for   p   ∈   Γ 1 ( λ, K,   i A ); =   λ,   for   p   ∈   ∂ Γ 1 ( λ, K,   i A );  > λ,   for   p   ∈   [Γ 1 ( λ, K, A )] c , γ 1 ( p, A )      ≤   λ,   for   p   ∈   Γ 1 ( λ, K, A );  6  =   λ,   for   p   ∈   [ ∂ Γ 1 ( λ, K,   i A )] c ;  ≥   λ,   for   p   ∈   [Γ 1 ( λ, K,   i A )] c .  (b) For   − r A   ≤   λ   ≤   0   we have  γ 1 ( p, A )      < λ,   for   p   ∈   i Γ 1 ( λ, K, A ); =   λ,   for   p   ∈   ∂ Γ 1 ( λ, K, A );  > λ,   for   p   ∈   [Γ 1 ( λ, K, A )] c , γ 1 ( p, A )      ≤   λ,   for   p   ∈   Γ 1 ( λ, K, A );  6  =   λ,   for   p   ∈   [ ∂ Γ 1 ( λ, K, A )] c ;  ≥   λ,   for   p   ∈   k [Γ 1 ( λ, K, A )] c .  Observation 2   For   λ   ≥   R A   we have  γ 2 ( p, A )      < λ,   for   p   ∈   i Γ 2 ( λ, K, A ); =   λ,   for   p   ∈   ∂ Γ 2 ( λ, K, A );  > λ,   for   p   ∈   [Γ 2 ( λ, K, A )] c , γ 2 ( p, A )      ≤   λ,   for   p   ∈   Γ 2 ( λ, K, A );  6  =   λ,   for   p   ∈   [ ∂ Γ 2 ( λ, K, A )] c ;  ≥   λ,   for   p   ∈   k [Γ 2 ( λ, K, A )] c .  It is clear that   inf p ∈ R n   { γ 1(2) ( p, A ) }   =   − r A ( R A ) . Generally, for   i   = 1 ,   2 , we get  γ i ( p, A )  {   ≤   λ,   for   p   ∈   Γ i ( λ, K, A );  > λ,   for   p   ∈   [Γ i ( λ, K, A )] c .   (7) The topological properties of families   Γ 1 , 2 ( λ, K, A )   have been studied in [42].  4 Correspondence between distances and the parametric families  Let us consider the translational distance   ω ( B, A )   between the objects   A   and   B .   We say that the distance   ω ( B, A )   corresponds   to the parametric family of objects   Ω( λ, K, B, A )   if and only if   ω ( B   +   p, A )   ≤   λ , for   p   ∈   Ω( λ, K, B, A ) .   (Clearly,   ω ( B   +   p, A )   > λ , for  p   ∈   [Ω( λ, K, B, A )] c , and   ω ( B, A )   ≤   λ , for   O   ∈   Ω( λ, K, B, A ) .) The correspondence be- tween   ω ( B, A )   and   Ω( λ, K, B, A )   is denoted by   ω ( B, A )   ∼   Ω( λ, K, B, A ) . In special case where an object   B   is the origin   O , the distance function   ω ( B   +   p, A )   is reduced to the distance   ω ( O   +   p, A ) =   ω ( p, A )   between a point   p   and an object   A , and the family of objects   Ω( λ, K, B, A )   is reduced to   Ω( λ, K, O, A ) = Ω( λ, K, A ) . Consider the families of objects   Γ 1 , 2 ( λ, K, A ) , and the distances   γ 1 , 2 ( O   +   p, A ) . 9
Lemma 3   For   i   = 1 ,   2   we have: (a)   γ i ( O, A )   ∼   Γ i ( λ, K, A ) . (b)   γ i ( ± p, A ) =   γ i ( O, A   ∓   p ) .  Follow from the relationship (7), and since   A ⊕{± ˇ p }   =   A   ∓   p . Since diam ( A ) = 2 R A , it can easily be shown that   γ 2 ( p, A ) =   diam ( { p } ∪   A )   > λ   if and only if   p   ∈   [Γ 2 ( λ, K, A )] c , for   λ   ≥   2 R A . Then we get diam ( { O } ∪   A )   ∼   Γ 2 ( λ, K, A ) , for  λ   ≥   2 R A . (Note that   γ 2 ( p, A )   ≤   diam ( { p }∪ A ) =   diam ( A ) =   λ   if and only if   p   ∈   Γ 2 ( λ, K, A ) , for   λ   ≤   2 R A .) The properties of the distances   γ 1 , 2 ( p, A )   and their corresponding families   Γ 1 , 2 ( λ, K, A )   in case where   A   =   ⋃ n j =1   A j   and/or   A   =   ⋂ n j =1   A j   , for   A   6   =   ∅ , have been studied in [42]. In general case where   B   is a geometric object, but not a single point, we have  Lemma 4   (a)   γ i ( B   +   p, A ) =   γ i ( B, A   −   p ) =   γ i ( p,   i A ⊕ i   ˇ B ) , for   i   = 1 ,   2 . (b)   γ i ( p,   i A ⊕ i   ˇ B ) =  γ i [ B   +   α   ·   p, A   −   (1   −   α )   ·   p ] , for   0   ≤   α   ≤   1 . (c)   γ i ( B θ   ±   p, A θ   ±   q ) =   γ i ( B θ   ∓   q, A θ   ∓   p ) =  γ i [ ± p   ∓   q,   ( i A ⊕ i   ˇ B ) θ ] , for   i   = 1 ,   2 .  Remark 1   For   i   = 2 , the sets   i A   and/or   i B   can be replaced by   A   and/or   B , respec- tively, since   sup {‖ c ‖ |   c   ∈   ∂ ( i A ⊕ i   ˇ B ) }   = sup {‖ c ‖ |   c   ∈   ∂ ( A ⊕   ˇ B ) } , i.e.,   γ 2 ( p,   i A ⊕ i   ˇ B ) =  γ 2 ( p, A ⊕   ˇ B ) .  Remark 2   By the first of relationships (5), we have   γ i ( B, A ) =   γ i ( B ∗ , A ∗ ) , for   i   = 1 ,   2 , where   A ∗   ∈ { A,   i A }   and   B ∗   ∈ { B,   i B } , respectively. Let us first consider the parametric family of objects  Γ 1 ( λ, K, B, A ) =  {   ( A ⊕   ˇ B ) ⊕ λK,   for   λ   ≥   0; ( A ⊕   ˇ B ) ⊖| λ | K,   for   −   r A ⊕   ˇ B   ≤   λ   ≤   0 ,  (see Figure 5(a)). Since   Γ 1 ( λ, K, B, A ) = Γ 1 ( λ, K, A ⊕   ˇ B ) , the object   Γ 1 ( − r A ⊕   ˇ B   , K, B, A )   is the locus of the centers of all largest inscribed balls in   A ⊕   ˇ B .  Observation 5   (a) For   λ   ≥   0   we have  γ 1 ( B   +   p, A )          ≤   λ,   for   p   ∈   Γ 1 ( λ, K, B, A );  < λ,   for   p   ∈   Γ 1 ( λ, K, B,   i A ); =   λ,   for   p   ∈   ∂ Γ 1 ( λ, K, B,   i A );  ≥   λ,   for   p   ∈   [Γ 1 ( λ, K, B,   i A )] c .  (b) For   − r i A ⊕ i   ˇ B   ≤   λ <   0   we have  γ 1 ( B   +   p, A )          ≤   λ,   for   p   ∈   Γ 1 ( λ,   i K,   i B,   i A );  < λ,   for   p   ∈   i Γ 1 ( λ,   i K,   i B,   i A ); =   λ,   for   p   ∈   ∂ Γ 1 ( λ,   i K,   i B,   i A );  ≥   λ,   for   p   ∈   k [Γ 1 ( λ,   i K,   i B,   i A )] c .  See Figures 5(a) and 6(a). Hence, the set  P   ( λ, K, B, A ) =   { p   |   γ 1 ( B   +   p, A ) =   λ }   =  {   ∂ Γ 1 ( λ, K, B,   i A )   for   λ   ≥   0;  ∂ Γ 1 ( λ,   i K,   i B,   i A ) ,   for   −   r i A ⊕ i   ˇ B   ≤   λ <   0 ,  is the surface of the function   γ 1 ( B   +   p, A ) , and   inf p ∈ R n   { γ 1 ( B   +   p, A ) }   =   − r i A ⊕ i   ˇ B   . Thus, we get 10
Theorem 6   γ 1 ( B, A )   ∼  {   Γ 1 ( λ, K, B, A ) ,   for   λ   ≥   0; Γ 1 ( λ,   i K,   i B,   i A ) ,   for   −   r i A ⊕ i   ˇ B   ≤   λ <   0 .  Note that in case where   λ   ≥   0   the Theorem 6 has also been proved in [37] and [56]. Denote by   d P   ( A, B )   the penetration depth of   A   and   B   (see [35]). In [42] it is shown that  γ 1 ( B, A ) =   − d P   ( i A,   i B ) , for   A   ∩   B   6   =   ∅ . Then we have   d P   ( A, B )   ∼   Γ 1 ( λ, K, B, A ) , for  − r A ⊕   ˇ B   ≤   λ <   0 . Let us next consider the parametric family of objects  Γ 2 ( λ, K, B, A ) =   λK ⊖ ( A ⊕   ˇ B ) ,   for   λ   ≥   R A ⊕   ˇ B   ,  proposed in [39] and [40]; see Figures 5(b) and 6(b). Since   Γ 2 ( λ, K, B, A ) = Γ 2 ( λ, K, A ⊕   ˇ B ) , the object   Γ 2 ( R A ⊕   ˇ B   , K, B, A )   is a singleton point, which is the center of the (unique) smallest enclosing ball of   A ⊕   ˇ B . The object   Γ 2 ( λ, K, B, A )   is convex, for any bounded   A   and   B , and  Γ 2 ( λ, K, B, A ) = Γ 2 [ λ, K, CH ( A ⊕   ˇ B )] = Γ 2 [ λ, K, ext ( A ⊕   ˇ B )] .  (b) (a)  y x  B  y x  B B   +   p   p p γ 1   ( B   +   p, A )  γ 2   ( B   +   p, A ) Γ 2 ( λ 2 , K, B, A )  A ∂ ( A ⊕   ˇ B )  A ∂ ( A ⊕   ˇ B )  B   +   p B   +   q  Γ 1 ( λ 1 , K, B, A )  q  Figure 5: The objects   Γ 1 , 2 ( λ 1 , 2 , K, B, A ) . Here   γ 1 , 2 ( B   +   p, A ) =   λ 1 , 2   and   λ 1   >   0 . A dotted line shows a piece of   ∂ Γ 1 ( λ 1 , K, B,   i A ) , and   γ 1 ( B   +   q, A ) =   λ 1 , for   q   ∈   ∂ Γ 1 ( λ 1 , K, B,   i A ) .  Observation 7   For   λ   ≥   R A ⊕   ˇ B   we have  γ 2 ( B   +   p, A )          ≤   λ,   for   p   ∈   Γ 2 ( λ, K, B, A );  < λ,   for   p   ∈   i Γ 2 ( λ, K, B, A ); =   λ,   for   p   ∈   ∂ Γ 2 ( λ, K, B, A );  ≥   λ,   for   p   ∈   k [Γ 2 ( λ, K, B, A )] c .  (Clearly,   inf p ∈ R n   { γ 2 ( B   +   p, A ) }   =   R A ⊕   ˇ B   .) Then we get the following:  Theorem 8   γ 2 ( B, A )   ∼   Γ 2 ( λ, K, B, A ) , for   λ   ≥   R A ⊕   ˇ B   .  By previous observations, we also obtain that   γ 2 ( B   +   p, A ) =   diam (( B   +   p )   ∪   A )   > λ   if and only if   p   ∈   [Γ 2 ( λ, K, B, A )] c , for   λ   ≥   2 R A ⊕   ˇ B   . Hence, diam ( B   ∪   A )   ∼   Γ 2 ( λ, K, B, A ) , for  λ   ≥   2 R A ⊕   ˇ B   . The additional (topological and set theoretic) properties of the distances   γ 1 , 2 ( B, A )   and the families   Γ 1 , 2 ( λ, K, B, A )   have been studied in [42]. 11
(b) (a)  y x y x  B   +   p   p γ 2   ( B   +   p, A ) Γ 2 ( λ 2 , K, B, A )  A q  Γ 1 ( λ 1 ,   i K,   i B,   i A )  B   B γ 1   ( B   +   p, A )  p B   +   p ∂ ( i A ⊕ i   ˇ B )   ∂ ( i A ⊕ i   ˇ B )  A  Figure 6: The objects (a)   Γ 1 ( λ 1 ,   i K,   i B,   i A )   and (b)   Γ 2 ( λ 2 , K, B, A ) . Here   γ 1 , 2 ( B + p, A ) =   λ 1 , 2  and   λ 1   <   0 . A dashed lines show   ∂ ( i A ⊕ i   ˇ B ) .  5 Distances between geometric objects concerning their inner relative posi- tion  The duality of the Minkowski operations provide estimating the   inner   relative position of geo- metric objects.  5.1 Distances concerning the containment of objects  Let us consider the following translational distances, introduced in [39] and [40]:  η 1 ( B, A ) =      inf c ∈ ∂ ( A ⊖   ˇ B )   ‖ c ‖ ,   for   B   6   ⊂   A ; 0 ,   for   B    ̇ ⊂ A ;  −   inf c ∈ ∂ ( A ⊖   ˇ B )   ‖ c ‖ ,   for   B ⊂ A, η 2 ( B, A ) =   sup  c ∈ ∂ ( A ⊖   ˇ B )  ‖ c ‖ .  See Figure 7. (The distances   η 1 , 2 ( B, A )   are defined only in case where   A ⊖   ˇ B   6   =   ∅ .) The properties of the distances   η 1 , 2 ( B, A )   have been studied in [39] and [41]. The distance  η 1 ( B, A )   (resp.,   η 2 ( B, A ) ) corresponds to the minimal (resp., maximal) translation   B   +   p   of   B  relative to   A   that reaches an inner touching   ( B   +   p )  ̇ ⊂ A . Since   ∂ ( A ⊖   ˇ B ) =   ∂ ( A c ⊕ i   ˇ B ) , we have  η 1 ( B, A ) =   − γ 1 ( B, A c )   and   η 1 ( B, A ) =   − d ∗ ( A, B ) , for   B ⊂ A .  Lemma 9   (a)   η i ( p, A ) =   γ i ( p, A ) , for   i   = 1 ,   2 . (b)   η i ( B   + p, A ) =   η i ( B, A − p ) =   η i ( p, A ⊖   ˇ B ) . (c)   η i [ B   +   α   ·   p, A   −   (1   −   α )   ·   p ] =   η i ( p, A ⊖   ˇ B ) , for   0   ≤   α   ≤   1 . (d)   η i ( B θ   ±   p, A θ   ±   q ) =  η i ( B θ   ∓   q, A θ   ∓   p ) =   η i [ ± p   ∓   q,   ( A ⊖   ˇ B ) θ ] , for   i   = 1 ,   2 .  It can easily be shown that  η 1 ( B, A )      <   0 ,   for   O   ∈   i ( A ⊖   ˇ B ); = 0 ,   for   O   ∈   ∂ ( A ⊖   ˇ B );  >   0 ,   for   O   ∈   ( A ⊖   ˇ B ) c .  12
(a)   (b)   (c)  x y x y x y  η 1   ( B, A )   <   0  A A   ⊖   ˇ B η 1   ( O, A   ⊖   ˇ B )   η 2   ( O, A   ⊖   ˇ B )   η 1 ( O, A   ⊖   ˇ B )  η 1   ( B, A )   >   0 A   ⊖   ˇ B   η 2 ( B, A )   A   ⊖   ˇ B B A B A O   O B O η 1 ( B, A ) = 0  Figure 7: The distances   η 1 , 2 ( B, A ) , for various relative positions of   A   and   B . Here (a)   B ⊂ A , (b)   B    ̇ ⊂ A , and (c)   B   6   ⊂   A , respectively. See Figure 7. The distances   η 1 , 2 ( B, A )   have used in [40] and [41] to describe the constraints on the relative position of objects in containment problems. Let us consider the following parametric families of objects [39], [40]:  H 1 ( λ, K, B, A ) =  {   ( A ⊖   ˇ B ) ⊕ λK,   for   λ   ≥   0; ( A ⊖   ˇ B ) ⊖| λ | K,   for   −   r A ⊖   ˇ B   ≤   λ   ≤   0 , H 2 ( λ, K, B, A ) =   λK ⊖ ( A ⊖   ˇ B ) ,   for   λ   ≥   R A ⊖   ˇ B   ,  See Figure 8.  (a)   (b)  A  x  η 1 ( B   +   p, A )  A  x y y  p B   B B   +   p H 1   ( λ 1   , K, B, A )  B   +   p H 2 ( λ 2   , K, B, A )  ∂ ( A   ⊖   ˇ B )   ∂ ( A   ⊖   ˇ B )  p η 2   ( B   +   p, A )  Figure 8: The objects   H 1 , 2 ( λ 1 , 2 , K, B, A ) . Here   η 1 , 2 ( B   +   p, A ) =   λ 1 , 2   and   λ 1   <   0 . 13
Observation 10   (a) For   λ >   0   we have  η 1 ( B   +   p, A )          ≤   λ,   for   p   ∈   H 1 ( λ, K, B, A );  < λ,   for   p   ∈   H 1 ( λ,   i K, B, A ); =   λ,   for   p   ∈   ∂H 1 ( λ,   i K, B, A );  ≥   λ,   for   p   ∈   [ H 1 ( λ,   i K, B, A )] c .  (b) For   i   = 1 ,   2 ,   − r A ⊖   ˇ B   ≤   λ 1   ≤   0 , and   λ 2   ≥   R A ⊖   ˇ B   , respectively, we have  η i ( B   +   p, A )          ≤   λ i ,   for   p   ∈   H i ( λ i , K, B, A );  < λ i ,   for   p   ∈   i H i ( λ i , K, B, A ); =   λ i ,   for   p   ∈   ∂H i ( λ i , K, B, A );  ≥   λ i ,   for   p   ∈   k [ H i ( λ i , K, B, A )] c .  Then   inf p ∈ R n   { η 1(2) ( B   +   p, A ) }   =   − r A ⊖   ˇ B   ( R A ⊖   ˇ B   ) . Thus, by above, we obtain the following:  Theorem 11   η i ( B, A )   ∼   H i ( λ, K, B, A ) , for   i   = 1 ,   2 .  The additional properties of the distances   η 1 , 2 ( B, A )   and the families   H 1 , 2 ( λ, K, B, A )   have been studied in [42].  5.2 Distances concerning the covering of objects  In this section we introduce the distances   δ 1 , 2 ( B, A )   involving the   covering   of   A   by   B :  δ 1 ( B, A ) =      inf c ∈ ∂ ( ˇ B ⊖ A )   ‖ c ‖ ,   for   A   6   ⊂   B ; 0 ,   for   A    ̇ ⊂ B ;  −   inf c ∈ ∂ ( ˇ B ⊖ A )   ‖ c ‖ ,   for   A ⊂ B, δ 2 ( B, A ) =   sup  c ∈ ∂ ( ˇ B ⊖ A )  ‖ c ‖ .  See Figure 9. (The distances   δ 1 , 2 ( B, A )   are defined only in case where   ˇ B ⊖ A   6   =   ∅ .)  (a)   (b)   (c)  x y x y x y  γ 1 ( O,   ˇ B   ⊖   A )   γ 2   ( O,   ˇ B   ⊖   A )   γ 1 ( O,   ˇ B   ⊖   A )  δ 2 ( B, A )  O   O O δ 1   ( B, A )   <   0  A B   B A B A δ 1   ( B, A )   >   0 ˇ B   ⊖   A   ˇ B   ⊖   A   ˇ B   ⊖   A δ 1 ( B, A ) = 0  Figure 9: The distances   δ 1 , 2 ( B, A ) , for various relative positions of   A   and   B . Here (a)   A ⊂ B , (b)   A    ̇ ⊂ B , and (c)   A   6   ⊂   B , respectively. The properties of the distances   δ 1 , 2 ( B, A )   and   η 1 , 2 ( B, A )   are similar. The distance   δ 1 ( B, A )  (resp.,   δ 2 ( B, A ) ) corresponds to the minimal (resp., maximal) translation   B   +   p   of   B   relative to   A   that reaches an inner touching   A    ̇ ⊂ ( B   +   p ) . The following helpful properties of   δ 1 , 2 ( B, A )  hold:   δ 1 ( B, A ) =   − γ 1 ( B c , A )   and   δ i ( B, A ) =   η i ( ˇ A,   ˇ B ) , for   i   = 1 ,   2 . 14
Lemma 12   (a)   δ i ( B   +   p, A ) =   δ i ( B, A   −   p ) =   δ i ( B ⊖   ˇ A,   − p ) =   γ i ( p,   ˇ B ⊖ A ) , for   i   = 1 ,   2 . (b)   δ i [ B   +   α   ·   p, A   −   (1   −   α )   ·   p ] =   δ i ( B ⊖   ˇ A,   − p ) , for   0   ≤   α   ≤   1 . (c)   δ i ( B θ   ±   p, A θ   ±   q ) =  δ i ( B θ   ∓   q, A θ   ∓   p ) =   δ i [( B ⊖   ˇ A ) θ ,   ∓ p   ±   q ] =   γ i [ ± p   ∓   q,   ( ˇ B ⊖ A ) θ ] , for   i   = 1 ,   2 .  It can easily be shown that  δ 1 ( B, A )      <   0 ,   for   O   ∈   i ( ˇ B ⊖ A ); = 0 ,   for   O   ∈   ∂ ( ˇ B ⊖ A );  >   0 ,   for   O   ∈   ( ˇ B ⊖ A ) c .  See Figure 9. The distances   δ 1 , 2 ( B, A )   can be used to formalize the constraints on the relative position of objects in covering problems. Let us consider the parametric families of objects  ∆ 1 ( λ, K, B, A ) =  {   ( ˇ B ⊖ A ) ⊕ λK,   for   λ   ≥   0; ( ˇ B ⊖ A ) ⊖| λ | K,   for   −   r   ˇ B ⊖ A   ≤   λ   ≤   0 ,  ∆ 2 ( λ, K, B, A ) =   λK ⊖ ( ˇ B ⊖ A ) ,   for   λ   ≥   R   ˇ B ⊖ A .  See Figure 10. Since   ∆ i ( λ, K, B, A ) =   − H i ( λ, K, A, B ) , for   i   = 1 ,   2 , we get  Observation 13   (a) For   λ >   0   we have  δ 1 ( B   +   p, A )          ≤   λ,   for   p   ∈   ∆ 1 ( λ, K, B, A );  < λ,   for   p   ∈   ∆ 1 ( λ,   i K, B, A ); =   λ,   for   p   ∈   ∂ ∆ 1 ( λ,   i K, B, A );  ≥   λ,   for   p   ∈   [∆ 1 ( λ,   i K, B, A )] c .  (b) For   i   = 1 ,   2 ,   − r   ˇ B ⊖ A   ≤   λ 1   ≤   0 , and   λ 2   ≥   R   ˇ B ⊖ A , respectively, we have  δ i ( B   +   p, A )          ≤   λ i ,   for   p   ∈   ∆ i ( λ i , K, B, A );  < λ i ,   for   p   ∈   i ∆ i ( λ i , K, B, A ); =   λ i ,   for   p   ∈   ∂ ∆ i ( λ i , K, B, A );  ≥   λ i ,   for   p   ∈   k [∆ i ( λ i , K, B, A )] c .  Thus,   inf p ∈ R n   { δ 1(2) ( B   +   p, A ) }   =   − r   ˇ B ⊖ A ( R   ˇ B ⊖ A ) . Hence, we can conclude  Theorem 14   δ i ( B, A )   ∼   ∆ i ( λ, K, B, A ) , for   i   = 1 ,   2 .  Note that the Theorem 14 also follows from the claim (a) of Lemma 12, and from the relation- ship   ∆ 1(2) ( λ, K, B, A ) = Γ 1(2) ( λ, K,   ˇ B ⊖ A ) . The additional properties of the distances   δ 1 , 2 ( B, A )   and the families   ∆ 1 , 2 ( λ, K, B, A )   have been studied in [42].  6 Hausdorff distances and corresponding families of objects  Since   H ( A, B ) = inf { λ   ≥   0   |   B ⊂ Γ 1 ( λ, K, A ) , A ⊂ Γ 1 ( λ, K, B ) }   [19], we have   h ( B, A ) = inf { λ   ≥   0   |   B ⊂ Γ 1 ( λ, K, A ) } .   Then   h ( B, A ) = 0   in case where   B ⊂ A , i.e., the distance  h ( B, A )   does not take into account the “amount” of containment of   B   in   A . 15
(b) (a)  O B A   ∂ ( ˇ B   ⊖   A )  p  y  O B  y  p  ∆ 1 ( λ 1 , K, B, A )  B   +   p   B   +   p  ∆ 2 ( λ 2   , K, B, A )  x   x  ∂ ( ˇ B   ⊖   A )  δ 1   ( B   +   p, A )  δ 2   ( B   +   p, A )  A  Figure 10: The objects (a)   ∆ 1 , 2 ( λ 1 , 2 , K, B, A ) . Here   δ 1 , 2 ( B   +   p, A ) =   λ 1 , 2   and   λ 1   <   0 . In [41] has been introduced the signed distance   μ ( B, A ) = sup b ∈ B   { γ 1 ( b, A ) } , eliminating this shortcoming, and it is shown that  μ ( B, A ) =  {   h ( B, A ) ,   for   B   6   ⊂   A ;  η 1 ( B, A ) ,   otherwise .  Then the signed distance   μ ( A, B )   can be defined as  μ ( A, B ) =  {   h ( A, B ) ,   for   A   6   ⊂   B ;  δ 1 ( B, A ) ,   otherwise .  Hence,   H ( A, B ) = max { μ ( A, B ) , μ ( B, A ) } . In [1] and [41] has been suggested the parametric family of objects   M 1 ( λ, K, B, A ) = Γ 1 ( λ, A ) ⊖   ˇ B , for   λ   ≥ − r A ⊖   ˇ B   , and it is shown that   μ ( B, A )   ∼   M 1 ( λ, K, B, A ) ; see Fig- ure 11(a). The family of objects   M 2 ( λ, K, B, A ) = Γ 1 ( λ,   ˇ B ) ⊖ A , for   λ   ≥   0 , has been intro- duced in [1], and it is shown (in our notation) that   h ( A, B )   ∼   M 2 ( λ, K, B, A ) , and   H ( A, B )   ∼  M 3 ( λ, K, B, A ) = [ M 1 ( λ, K, B, A )   ∩ M 2 ( λ, K, B, A )] , respectively. See Figure 11(b). Clearly, for   − r   ˇ B ⊖ A   ≤   λ   ≤   0 , we have   μ ( A, B )   ∼   M 2 ( λ, K, B, A ) . For notational convenience, the distances   μ ( B, A ) ,   μ ( A, B ) , and   H ( A, B )   are sometimes denoted by   m 1 ( B, A ) ,   m 2 ( B, A ) , and   m 3 ( B, A ) , respectively. Then we get  Theorem 15   m i ( B, A )   ∼   M i ( λ, K, B, A ) , for   i   = 1   −   3 .  The objects   M 1 − 3 ( λ, K, B, A )   have the following simple properties:  M 1(2) ( λ, K, B, A ) =   − M 2(1) ( λ, K, A, B );   M 3 ( λ, K, B, A ) =   − M 3 ( λ, K, A, B ) .  Observation 16   (a) For   i   = 1   −   3 , and   λ >   0   we have  m i ( B   +   p, A )          ≤   λ,   for   p   ∈   M i ( λ, K, B, A );  < λ,   for   p   ∈   i M i ( λ,   i K,   i B,   i A ); =   λ,   for   p   ∈   M i ( λ, K, B, A ) \ i M i ( λ,   i K,   i B,   i A );  ≥   λ,   for   p   ∈   k [ M 1 ( λ,   i K,   i B,   i A )] c .  16
(a)   (b)  y  A p  x  B  y x  p A B   +   p μ ( B   +   p, A )   μ ( A, B   +   p ) ˇ B ∂ ( A   ⊖   ˇ B )  M 2   ( λ 2 , K, B, A )  B   +   p M 1   ( λ 1   , K, B, A )  ∂ Γ 1   ( λ 1 , K, A )  Figure 11:   The objects (a)   M 1 , 2 ( λ 1 , 2 , K, B, A ) .   Here, respectively,   μ ( B   +   p, A ) =   λ 1   >  0 ,   μ ( A, B   +   p )   =   λ 2   >   0 , and   ∂ Γ 1 ( λ 1 , K, A )   =   ∂ Γ 1 ( λ 1 ,   i K,   i A ) ,   ∂ Γ 1 ( λ 2 , K,   ˇ B )   =  ∂ Γ 1 ( λ 2 ,   i K,   i   ˇ B ) .  (b) For   i   = 1 ,   2 ,   − r A ⊖   ˇ B   ≤   λ 1   ≤   0 , and   − r   ˇ B ⊖ A   ≤   λ 2   ≤   0   we have  m i ( B   +   p, A )          ≤   λ i ,   for   p   ∈   M i ( λ i , K, B, A );  < λ i ,   for   p   ∈   i M i ( λ i , K, B, A ); =   λ i ,   for   p   ∈   ∂M i ( λ i , K, B, A );  ≥   λ i ,   for   p   ∈   k [ M i ( λ i , K, B, A )] c .  Remark 3   In [42] it is shown that, in contrast to the distances considered in Sections 2 – 5, the region where the distance   μ ( B   +   p, A )   (resp.,   μ ( A, B   +   p ) ) is equal to   λ   may have the non-empty interior. The additional properties of the Hausdorff distances and their corresponding families have been studied in [42].  7 Translational distances between geometric objects and translational geo- metric situations  The distances considered in Sections 2 – 6 are referred to as the   translational   distances (or   T   - distances). Let   T D ( B, A ) =   { γ 1 , 2 ( B, A ) , η 1 , 2 ( B, A ) , δ 1 , 2 ( B, A ) , m 1 − 3 ( B, A ) }   be a collection of the   T   -distances between   B   and   A , and let   ω ( B, A )   ∈ T D ( B, A ) . The   T   -distances   ω ( B, A )  and their corresponding families   Ω( λ, K, B, A )   have the following properties:  ω ( B   +   p, A ) =   ω ( B, A   −   p ) =   ω [ B   +   α   ·   p, A   −   (1   −   α )   ·   p ] ,   for   0   ≤   α   ≤   1;  ω ( B θ   ±   p, A θ   ±   q ) =   ω ( B θ   ∓   q, A θ   ∓   p ); Ω( λ 1 , K, B, A ) ⊆ Ω( λ 2 , K, B, A ) ,   for any bounded   A   and   B , and   λ 1   ≤   λ 2 ; Ω[ λ, K, B   +   α   ·   p, A   −   (1   −   α )   ·   p ] = Ω( λ, K, B, A )   −   p,   for   0   ≤   α   ≤   1;  17
Ω( λ, K, B θ   ±   p, A θ   ±   q ) = Ω( λ, K, B θ   ∓   q, A θ   ∓   p ) = [Ω( λ, K, B, A )] θ   ∓   p   ±   q.  From the last relationship it follows that   ω ( B   ±   p, A   ±   q )   ≤   λ , for   ± p   ∓   q   ∈   Ω( λ, K, B, A ) . By the previous observations, we get  ( A   ∩   B   =   ∅ )   ∧   ( B   6   ⊂   A )   ⇐⇒   [ γ 1 ( B, A )   >   0 ] ∧ {[ η 1 ( B, A )   >   0 ] ∨ [ μ ( B, A )   >   0 ]}  ; ( A   ∩   B   6   =   ∅ )   ∧   ( A ⊂ B )   ⇐⇒   [ γ 1 ( B, A )   ≤   0 ] ∧ {[ δ 1 ( B, A )   ≤   0 ] ∨ [ μ ( A, B )   ≤   0 ]}  .  Hence, the various situations of the relative position of objects   A   and   B   can be described by the system of constraints on the   T   -distances between   A   and   B .  Definition 17   The relationship   ν ( B   +   p, A ) = [ ω ( B   +   p, A )   ⊙   λ ] , where   ⊙ ∈ { <,   = , > } , is called the primitive translational geometric situation (PTGS) of an object   B   with respect to an object   A .  Let us consider the PTGS   ν ( B   +   p, A )   as an event.   Then the class of all the possible PTGS’s   S + ( B, A )   forms an   algebra   A T   of events [23]. For   S + ( B, A )   permitting the following definitions: 1. The   union   of events:   ν 1 ( B   +   p, A )   ∨   ν 2 ( B   +   p, A ) . 2. The   intersection   of events:   ν 1 ( B   +   p, A )   ∧   ν 2 ( B   +   p, A ) . 3. The   complement   of event:   [ ν ( B   +   p, A )] c . 4. The   certain   event   I   is the union of all the PTGS’s in   S + ( B, A ) . 5. The   impossible   event   0   is an impossible relative position of objects, for given   ν ( B   + p, A ) . The class   S ( B, A )   of PTGS’s, comprising   S + ( B, A )   and   0 , forms a completely additive Boolean algebra; see [23]. Let us consider the union of PTGS’s. (Recall that   ω ( B, A )   ∈ T D ( B, A ) .) Then we get  [ ω ( B   +   p, A )   ≤   λ ] = [ ω ( B   +   p, A )   < λ ]   ∨   [ ω ( B   +   p, A ) =   λ ]; [ ω ( B   +   p, A )   6   =   λ ] = [ ω ( B   +   p, A )   < λ ]   ∨   [ ω ( B   +   p, A )   > λ ];   (8)  [ ω ( B   +   p, A )   ≥   λ ] = [ ω ( B   +   p, A )   > λ ]   ∨   [ ω ( B   +   p, A ) =   λ ] .  (Clearly,   [ ω ( B   +   p, A )   < λ ]   ∧   [ ω ( B   +   p, A )   > λ ] = 0 .)   We define also the TGS of type  [ ω ( B   +   p, A )   →   min] , since in Sections 4 – 6 have been obtained the possible minimal values of the   T   -distances. We next add these TGS’s to the set of PTGS’s:  Definition 18   The relationship   ν ( B   +   p, A ) = [ ω ( B   +   p, A )   ⊙   λ   or   ω ( B   +   p, A )   →   min] , where   ⊙ ∈ { <,   ≤ ,   = ,   6   = ,   ≥ , > } , is called the basic translational geometric situation (BTGS) of  B   relative to   A .  Since   [ ω ( B   +   p, A )   < λ ] c   = [ ω ( B   +   p, A )   ≥   λ ] ,   [ ω ( B   +   p, A ) =   λ ] c   = [ ω ( B   +   p, A )   6   =   λ ] , and  [ ω ( B   +   p, A )   > λ ] c   = [ ω ( B   +   p, A )   ≤   λ ] , then, by the relationships of (8), and, by DeMorgan’s laws, we obtain the following useful relationships:  [ ω ( B   +   p, A )   < λ ] = [ ω ( B   +   p, A )   ≤   λ ]   ∧   [ ω ( B   +   p, A )   6   =   λ ]; [ ω ( B   +   p, A ) =   λ ] = [ ω ( B   +   p, A )   ≤   λ ]   ∧   [ ω ( B   +   p, A )   ≥   λ ]; [ ω ( B   +   p, A )   > λ ] = [ ω ( B   +   p, A )   ≥   λ ]   ∧   [ ω ( B   +   p, A )   6   =   λ ] .  18
Definition 19   The Boolean function   ν ( B + p, A ) =   f   [ ν 1 ( B + p, A ) , . . . , ν k ( B + p, A )]   of BTGS’s  ν i ( B   +   p, A ) , for   i   = 1 , . . . , k , is called the translational geometric situation (TGS) of   B   with respect to   A .  A particular TGS describes the constraints on the relative position of objects, and can be used as the   objective function   in the spatial planning problems.  8 Constructing the feasible region of an object for given translational geo- metric situation  Let   Ω( λ, K, B, A )   is the corresponding family of the distance   ω ( B, A ) . From the observations of Sections 4 – 6, and from the Definition 18 it follows that, for given BTGS   ν ( B   +   p, A ) , all the feasible translations   B   +   p   of   B   with respect to   A   are obtained if and only if   p   belongs to the region   N ( B, A ) , where   ν ( B   +   p, A )   is true. For example,  ν 1 ( B   +   p, A ) = [ ω ( B   +   p, A )   ≤   λ 1 ]   ⇐⇒   p   ∈   N 1 ( B, A ) = Ω( λ 1 , K, B, A );  ν 2 ( B   +   p, A ) = [ ω ( B   +   p, A )   > λ 2 ]   ⇐⇒   p   ∈   N 2 ( B, A ) = [Ω( λ 2 , K, B, A )] c .  The correspondence between   ν ( B   +   p, A )   and   N ( B, A )   is denoted by   ν ( B   +   p, A )   ∼   N ( B, A ) . Consider the TGS   ν ( B   +   p, A ) =   ν 1 ( B   +   p, A )   ∧   ν 2 ( B   +   p, A ) , where the BTGS’s   ν 1 , 2 ( B   +  p, A )   are as above. Clearly, its corresponding region is   N ( B, A ) =   N 1 ( B, A )   ∩   N 2 ( B, A ) . In case where   λ 1   ≤   λ 2 , we have   N ( B, A ) =   ∅ , and therefore   ν ( B   +   p, A )   is an impossible TGS, i.e.,   ν ( B   +   p, A ) = 0 . For the TGS   ν ( B   +   p, A ) =   ν 1 ( B   +   p, A )   ∨   ν 2 ( B   +   p, A )   we have  N ( B, A ) =   N 1 ( B, A )   ∪   N 2 ( B, A ) . If   λ 1   ≥   λ 2   then   N ( B, A ) =   R n . (Note that in this case  ν ( B   +   p, A )   6   =   I .) Consider next the TGS   ν ( B   + p, A ) = [ ω ( B   + p, A )   ≤   λ 1 ] ∨ [ ω ( B   + p, A )   ≤   λ 2 ] , where   λ 1   ≤  λ 2 . Then   N ( B, A ) = Ω( λ 1 , K, B, A )   ∪   Ω( λ 2 , K, B, A )   and   Ω( λ 1 , K, B, A ) ⊆ Ω( λ 2 , K, B, A ) , for   λ 1   ≤   λ 2 . Hence,   N ( B, A ) = Ω( λ 2 , K, B, A ) . That is, the TGS   ν ( B + p, A )   corresponding to the region   N ( B, A )   can be represented in different ways, e.g., as   ν ( B   +   p, A ) = [ ω ( B   +   p, A )   ≤  λ 2 ]   or   ν ( B + p, A ) =   ∨ n i =1 [ ω ( B + p, A )   ≤   λ i ] , where   λ i   ≤   λ 2 , for   i   = 1 , . . . , n . Thus, in general, the TGS   ν ( B   +   p, A )   does not unique relative to its corresponding region   N ( B, A ) . However, for given   N ( B, A ) , the unique (minimal) corresponding TGS   ν ( B   +   p, A )   can be constructed. Finally, if in the above example, we let   N ( B, A ) = Ω( λ, K, B, A )   ∪   Ω( λ 2 , K, B, A ) , where  λ 1   < λ   ≤   λ 2 , then we obtain that the TGS   [ ω ( B   +   p, A )   ≤   λ 1 ]   does not corresponds to the region   Ω( λ, K, B, A ) , however   ν ( B   +   p, A )   ∼   N ( B, A )   in this case. Therefore, we get the following:  Proposition 20   (a) The TGS   ν ( B   +   p, A ) =   f   [ ν 1 ( B   +   p, A ) , . . . , ν k ( B   +   p, A )]   corresponds to the region   N ( B, A ) =   F   [ N 1 ( B, A ) , . . . , N k ( B, A )]   if (but not only if)   ν i ( B   + p, A )   ∼   N i ( B, A ) , for   i   = 1 , . . . , k , and the operations of union, intersection, and complement of the BTGS’s  ν i ( B   + p, A )   of   ν ( B   + p, A )   correspond to the operations of union, intersection, and complement of regions   N i ( B, A )   of   N ( B, A ) . (b)   ν ( B   + p, A )   is an impossible TGS if and only if   N ( B, A ) =  ∅ . (c)   ν ( B   +   p, A )   is a certain TGS only if (but not if)   N ( B, A ) =   R n .  The region   N ( B, A )   is called the   solution   of the TGS   ν ( B   +   p, A ) .   (Note that the region  N i ( B, A )   of   N ( B, A )   is solution of the BTGS   ν i ( B   +   p, A ) , for   i   = 1 , . . . , k .) 19
Remark 4   Let   ν ( B   +   p, A )   be the BTGS concerning the   T   -distance   ω ( B   +   p, A ) , and let  ω ( B   +   p, A )   ∼   Ω( λ, K, B, A ) , and   ν ( B   +   p, A )   ∼   N ( B, A ) , respectively. In the next paragraph we assume, for simplicity, that the region   N ( B, A )   does not have coincident faces/edges and/or isolated points, which are removed from the interiors of the objects of   Ω( λ, K, B, A ) , for any  λ . Then we get  ω ( B   +   p, A )          ≤   λ,   for   p   ∈   Ω( λ, K, B, A );  < λ,   for   p   ∈   i Ω( λ, K, B, A ); =   λ,   for   p   ∈   ∂ Ω( λ, K, B, A );  ≥   λ,   for   p   ∈   k [Ω( λ, K, B, A )] c .  In this special case the set   ∂ Ω( λ, K, B, A )   is the surface of the function   ω ( B   +   p, A ) . The types of objects satisfying the above assumption are sufficiently wide. For example, the convex objects, the polygons/polytops and/or curved objects in general position, i.e., which do not have parallel edges/faces. Thus, one can to construct the solution of a particular TGS according to the more simpler relationships than that is done in Sections 4 – 6. See [42] for details.  Examples.   Consider the TGS’s   ν l ( B   +   p, A )   and their solutions   N l ( B, A ) , denoted by   ν l ,   N l , for short. Denote also   ω ( B   +   p, A ) ,   Ω( λ, K, B, A )   by   ω ,   Ω( λ ) . Below we let   i ( j ) = 1 ,   2 .  1   ν 1   = ( γ i   ≤   λ i )   ∧   ( γ j   ≥   λ j   );   N 1   = Γ i ( λ i )   ∩   k [Γ j   ( λ j   )] c   = Γ i ( λ i ) \ i Γ j   ( λ j   ) .  1a   ν 1 a   = ( γ i   < λ i )   ∧   ( γ j   > λ j   );   N 1 a   =   i Γ i ( λ i )   ∩   [Γ j   ( λ j   )] c   =   i Γ i ( λ i ) \ Γ j   ( λ j   ) .  1b   ν 1 b   = ( γ i   ≤   λ i )   ∧   ( γ j   > λ j   );   N 1 b   = Γ i ( λ i )   ∩   [Γ j   ( λ j   )] c   = Γ i ( λ i ) \ Γ j   ( λ j   ) .  1c   ν 1 c   = ( γ i   ≥   λ i )   ∧   ( γ j   ≥   λ j   );   N 1 c   =   k [Γ i ( λ i )] c   ∩   k [Γ j   ( λ j   )] c   =   k [Γ i ( λ i )   ∪   Γ j   ( λ j   )] c .  2   ν 2   = ( γ i   =   λ i )   ∧   ( γ j   =   λ j   );   N 2   =   ∂ Γ i ( λ i )   ∩   ∂ Γ j   ( λ j   ) .  3   ν 3   = ( γ 1   ≥   λ 1 )   ∧   ( γ 2   →   min) ,   where   λ 1   6   =   r ( A ⊕   ˇ B ) ;  N 3   =   k [Γ 1 ( λ 1 )] c   ∩   Γ 2 ( R A ⊕   ˇ B   ) = Γ 2 ( R A ⊕   ˇ B   ) \ i Γ 1 ( λ 1 ) .  4   ν 4   = ( η 1   →   min);   N 4   =   H 1 ( − r A ⊖   ˇ B   ) .  5   ν 5   = ( η 1   ≤   λ 1   ≤   0)   ∧   ( η 2   →   min);   N 5   =   H 1 ( λ 1 )   ∩   H 2 ( R A ⊖   ˇ B   ) .  6   ν 6   = [( γ 1   =   λ 1 )   ∧   ( γ 2   =   λ min )]   6   = 0;   N 6   =   ∂ Γ 1 ( λ 1 )   ∩   ∂ Γ 2 ( λ min ) ,  where   λ min   =  {   inf { λ   |   Γ 2 ( λ )  ̇ ⊂ Γ 1 ( λ 1 ) } ,   for   Γ 2 ( R A ⊕   ˇ B   )   ∈   Γ 1 ( λ 1 ); inf { λ   |   Γ 2 ( λ )  ̇ ∩ Γ 1 ( λ 1 ) } ,   for   Γ 2 ( R A ⊕   ˇ B   )   / ∈   Γ 1 ( λ 1 ) .  See Figure 12. The analysis of the Examples 1 – 6 can be found in [42].  Remark 5   The region   N ( B, A )   may have various topology. It can be open or closed, regular or non-regular, bounded or unbounded, connected or disconnected. So, in the above examples the region   N 1   is closed bounded, whereas the region   N 1 a   is open bounded; the region   N 1 c   is closed unbounded. In case where   N ( B, A )   contains the subset of its boundary, it is neither open nor closed. Thus, in general,   N ( B, A )   is an object with   non-manifold   boundary. The region  N 1 b   give an example of such an object. In case where   i   =   j ,   λ i   > λ j   , and   λ i,j   >   0 , respectively, the object   N 1   is regular, i.e., N 1   = Γ i ( λ i ) \ ∗ Γ j   ( λ j   ) . (Note that in case where   λ i   =   λ j   we get  N 1   =   ∂ Γ i ( λ i ) , i.e., the object   N 1   is non-regular.) 20
A ∂ ( A ⊕   ˇ B )  B O x   x  A ∂ ( A   ⊖   ˇ B )  ∂ Γ 2 ( λ 2   )  ∂ Γ 1   ( λ 1 )  ∂ Γ 2 ( λ min )  p 1 p 2  N 1  N 4  N 3  q 1 q 3  q 2  y   y  Figure 12:   The corresponding regions   N l   of TGS’s   ν l , for   l   =   1 , . . . ,   6 , in case where  Γ 2 ( R A ⊕   ˇ B   )   6   ∈   Γ 1 ( λ 1 ) .   Here   i   = 2 ,   j   = 1 , and   λ 1   < λ 2 , respectively.   The region   N 1   is simply connected,   N 2   =   { p 1 , p 2 } , and   N 3   = Γ 2 ( R A ⊕   ˇ B   ) , respectively. The region   N 4   is a curve,  N 5   =   ∅ , and   N 6   =   { q 1 , q 2 , q 3 } . Let us next consider the following problem:  Problem II   Find the region   N II   , corresponding to the TGS  ν II   =   [ ( λ 1   ≤   γ 1   ≤   λ 2 )   ∧   ( λ 3   ≤   γ 2   ≤   λ 4 ) ]   ∨   [ ( λ 5   ≤   η 1   ≤   λ 6 )   ∧   ( λ 7   ≤   η 2   ≤   λ 8 ) ] .  By Example 1, the solution is the region  N II   =  {[ Γ 1 ( λ 2 ) \ i Γ 1 ( λ 1 ) ]   ∩   [ Γ 2 ( λ 4 ) \ i Γ 2 ( λ 3 ) ]}  ∪  {[ H 1 ( λ 6 ) \ i H 1 ( λ 5 ) ]   ∩   [ H 2 ( λ 8 ) \ i H 2 ( λ 7 ) ]}  .  See Figure 13. Note that in case where   λ 1   > λ 2   or   λ 3   > λ 4 , and   λ 5   > λ 6   or   λ 7   > λ 8   we have  N II   =   ∅   and   ν II   = 0 . Let us turn to solve the problem, formulated in subsection 1.3. The following regions   N ′  I   , for   ⊙ 1   =   ∧ ,   ⊙ 2   =   ∨ , and   N ′′  I   , for   ⊙ 1   =   ∨ ,   ⊙ 2   =   ∧ , are the solutions of the Problem I:  N ′  I   =   [ Γ 1 ( λ 1 ) \ i Γ 1 ( λ 2 ) ]   ∪   [ Γ 2 ( λ 3 ) \ i Γ 2 ( λ 4 ) ]   ∪   [ H 1 ( λ 5 ) \ i H 1 ( λ 6 ) ] ;  N ′′  I   =   [ Γ 1 ( λ 1 )   ∪   k [Γ 1 ( λ 2 )] c ]   ∩   [Γ 2 ( λ 3 )   ∪   k [Γ 2 ( λ 4 )] c ]   ∩   [ H 1 ( λ 5 )   ∪   k [ H 1 ( λ 6 )] c ] .  Clearly, if   λ 1   < λ 2 ,   λ 3   < λ 4 , and   λ 5   < λ 6 , then   N ′  I   =   ∅   and   ν ′  I   = 0 . In case where   λ 1   ≥   λ 2 ,  λ 3   ≥   λ 4 , and   λ 5   ≥   λ 6   we have   N ′′  I   =   R d . (However,   ν ′′  I   6   =   I   in this case.) The additional properties of the TGS’s have been studied in [42].  9 Applications  In this section we consider the spatial planning problems with more general and more complex constraints on the distances between geometric objects. We also briefly consider the several other types of geometric situations: the translational geometric situation in a given direction, the rotational, and the dynamic geometric situations, respectively. 21
y x  B ∂ ( A ⊕   ˆ B )  ∂ ( A   ⊖   ˆ B )  A  y x  A O N II  N II  Figure 13: Illustration for the Problem II. Here the region   N II   is 5-connected.  9.1 Findspace problem  Let   A   =   { A 1 , . . . , A n }   be a collection of   n , possibly intersecting, obstacles   A i , completely contained in the region   R , and let   B   be the object moving relative to   A   under translations. See Figure 14(a). (For notational convenience, we also denote   A   =   ⋃ n i =1   A i .) The   translational   Findspace problem [29] is to find all the possible translations   ( B   +   p ) ⊂ R , such that   ( B   +   p )   ∩ A   =   ∅ . In this case   p   is called the   free   position. (If   ( B   +   p )  ̇ ∩A , then   p   is called the   semi-free   position [4].) The C-space obstacle of   B   relative to   A   is defined as   CO B   ( A ) =   { p   |   ( B   +   p )   ∩ A 6   =  ∅}   =   A⊕   ˇ B   =   ⋃ n i =1   CO B   ( A i ) =   ⋃ n i =1 ( A i ⊕   ˇ B )   [29].   (The object   [ CO B   ( A )] c   is called the  free C-space   of   B   relative to   A .) The C-space   interior   of   B   relative to the region   R   is defined as   CI B   ( R ) =   { p   |   ( B   +   p ) ⊆ R }   = [ CO B   ( R c )] c ; see Figure 14(a). By the definition of the Minkowski difference, we get   CI B   ( R ) =   R ⊖   ˇ B . In [14] it is shown that the set of all the feasible positions of   B   relative to   A   and   R   can be represented as   F P B   ( A , R ) = ( R \A ) ⊖   ˇ B   = ( R ⊖   ˇ B ) \ ( A⊕   ˇ B ) =   CI B   ( R ) \ CO B ( A ) ; see Figure 14(a). Let us consider the Findspace problem in terms of the translational geometric situations (TGS), studied in Sections 7 and 8. The conditions   ( B   +   p ) ⊂ R   and   ( B   +   p )   ∩ A   =   ∅   can be formalized as   [ η 1 ( B   +   p, R )   ≤   0]   and   [ γ 1 ( B   +   p,   A )   >   0] , respectively. In [42] it is shown that   [ γ 1 ( B   +   p,   A )   >   0] =   ∧ n i =1 [ γ 1 ( B   +   p, A i )   >   0] .   Then the Findspace problem can be reformulated as follows: Find the region   N ( B,   A , R )   corresponding to the TGS  ν ( B   +   p,   A , R ) =  [  η 1 ( B   +   p, R )   ≤   0  ] ∧ {   n ∧  i =1  [  γ 1 ( B   +   p, A i )   >   0  ]}  .  22
(a)   (b)  B  x y  A 1  A 2  A 3  R ∂ [ CI B   ( R )]  x O y  A 3  A 1  A 2  R N III   ( B,   A , R ) F P B   ( A , R )  p 1  B   +   p 1  p 2  B   +   p 2  Figure 14: The translational Findspace problem in case where   A   =   { A 1 , A 2 , A 3 } . (a) Here the region   F P B   ( A , R )   is connected, and   p 1 , 2   are the free positions of   B .   Dashed lines show   ∂ [ CO B   ( A )]   and   ∂ [ CI B   ( R )] , respectively.   (b) Illustration for the Problem III. Here  N III   ( B,   A , R )   is a two-connected region and   λ 1   = 0 ,   λ 2   =   | λ R | , and   λ 3   = 1 . 5 · λ 2 , respectively. Dashed curves show   ∂ [ CO B   ( λ A ,   A )]   and   ∂ [ CI B   ( λ R , R )] . Since   [ γ 1 ( B   +   p, A i )   >   0] = [ γ 1 ( B   +   p, A i )   ≤   0] c , we have   ∧ n i =1  [ γ 1 ( B   +   p, A i )   >   0 ]   =  { ∨ n i =1 [ γ 1 ( B   +   p, A i )   ≤   0] } c . Hence, the solving of the Findspace problem can be represented as follows:  N ( B,   A , R ) =   H 1 (0 , K, B, R )   ⋂ {   n ⋂  i =1  [  Γ 1 (0 , K, B, A i )  ] c }  =   H 1 (0 , K, B, R )   ⋂ [   n ⋃  i =1  Γ 1 (0 , K, B, A i )  ] c  =   H 1 (0 , K, B, R )   ⋂ [  Γ 1  (  0 , K, B,  n ⋃  i =1  A i  )] c  =   H 1 (0 , K, B, R ) ∖ Γ 1 (0 , K, B,   A ) .  Clearly,   H 1 (0 , K, B, R ) =   CI B   ( R )   and   Γ 1 (0 , K, B,   A ) =   CO B   ( A ) . We next consider more general Findspace problems.  Problem III   Find the corresponding region   N III   ( B,   A , R )   of the TGS  ν III   ( B   +   p,   A , R ) =  [  η 1 ( B   +   p, R )   ≤   λ R   ≤   0  ] ∧ {   n ∧  i =1  [  γ 1 ( B   +   p, A i )   > λ i   ≥   0  ]}  .  Solving the Problem III.   For given TGS   ν III   ( B   +   p,   A , R ) , the C-space obstacle depends on  λ A   =   { λ i } n i =1 , corresponds to the TGS   ∨ n i =1 [ γ 1 ( B   +   p, A i )   ≤   λ i ] , and therefore it can be represented as   CO B   ( λ A ,   A ) =   ⋃ n i =1   Γ 1 ( λ i , K, B, A i ) . The interior C-space corresponding to 23
the TGS   [ η 1 ( B   +   p, R )   ≤   λ R   ≤   0]   is the region   CI B   ( λ R , R ) =   H 1 ( λ R , K, B, R ) . (See Sections 4, 5, and Figure 14(b).) Thus, we get  N III   ( B,   A , R ) =   H 1 ( λ R , K, B, R )   ⋂ {   n ⋂  i =1  [  Γ 1 ( λ i , K, B, A i )  ] c }  =   H 1 ( λ R , K, B, R ) ∖[   n ⋃  i =1  Γ 1 ( λ i , K, B, A i )  ]  .  Problem IV   Find the solution   N IV   ( B,   A )   of the TGS  ν IV   ( B   + p,   A ) =  [  γ l 1   ( B   + p,   A )   ≤   λ 1  ] ∧ [  γ l 2   ( B   + p,   A )   > λ 2  ]  ,   where   l 1(2)   = 1 ,   2;   λ 1(2)   ≥   0 .  Solving the Problem IV.   The general solution is the region  N IV   ( B,   A ) = Γ l 1   ( λ 1 , K, B,   A )   ⋂ [  Γ l 2   ( λ 2 , K, B,   A )  ] c  = Γ l 1   ( λ 1 , K, B,   A ) \ Γ l 2   ( λ 2 , K, B,   A ) .  By observations of [42] and of Section 8, in case where   l 1(2)   = 1   and   λ 1(2)   ≥   0 , we have  ν IV   ( B   +   p,   A ) =  {   n ∨  i =1  [  γ 1 ( B   +   p, A i )   ≤   λ 1  ]} ∧ {   n ∧  i =1  [  γ 1 ( B   +   p, A i )   > λ 2  ]}  ;  N IV   ( B,   A ) =  [   n ⋃  i =1  Γ 1 ( λ 1 , K, B, A i )  ]∖[   n ⋃  i =1  Γ 1 ( λ 2 , K, B, A i )  ]  ,  whereas, for   l 1(2)   = 2   and   λ 1(2)   ≥   min 1 ≤ i ≤ n { R A i ⊕   ˇ B   } , we get  ν IV   ( B   +   p,   A ) =  {   n ∧  i =1  [  γ 2 ( B   +   p, A i )   ≤   λ 1  ]} ∧ {   n ∨  i =1  [  γ 2 ( B   +   p, A i )   > λ 2  ]}  ;  N IV   ( B,   A ) =  [   n ⋂  i =1  Γ 2 ( λ 1 , K, B, A i )  ]∖[   n ⋂  i =1  Γ 2 ( λ 2 , K, B, A i )  ]  .  See Figure 15. Note that   ν IV   ( B   +   p,   A ) = 0   and   N IV   ( B,   A ) =   ∅ , for   λ 1   ≤   λ 2 . Finally, we consider the Findspace problem concerning the   covering   of objects.  Problem V   Find the region   N V   ( B   + p,   A )   of all the possible coverings of object   A   by object  B   +   p , for given TGS  ν V   ( B   +   p,   A ) =  {   n ∨  i =1  [  δ 2 ( B   +   p, A i )   ≤   ε i  ]} ∧ {   n ∧  i =1  [  λ −  i   ≤   δ 1 ( B   +   p, A i )   ≤   λ +  i   ≤   0  ]}  .  The solution is  N V   ( B   +   p,   A ) =  [   n ⋃  i =1  ∆ 2 ( ε i , K, B, A i )  ] ⋂ {   n ⋂  i =1  [  ∆ 1 ( λ +  i   , K, B, A i ) ∖ i ∆ 1 ( λ −  i   , K, B, A i )  ]}  .  For more simple constraint   ν V   ( B   +   p,   A ) =   ∧ n i =1 [ δ 1 ( B   +   p, A i )   ≤   λ i   ≤   0] , we get   N V   ( B,   A ) = ⋂ n i =1   ∆ 1 ( λ i , K, B, A i ) ; see Figure 16. 24
(a)   (b)  x O   O N IV   ( B,   A )  A 1   A 2   A 1   A 2  x y y  N IV   ( B,   A )  Figure 15: Illustration for the Problem IV. Here   A   =   { A 1 , A 2 } , both   A 1   and   A 2   are line seg- ments,   B   =   { O } ,   λ 1   > λ 2 , and the region   N IV   ( B,   A )   is connected. Dashed curves show pieces of   ∂ Γ l 1 ( l 2   ) ( λ 1(2) , B, A 1(2) ) . Here (a)   l 1(2)   = 1 , and (b)   l 1(2)   = 2 .  9.2 Placement of geometric objects  An approches commonly used for solving the placement problems are the   sequential-single  method, suggested in [53] and [57], and the   multiple   placement of several objects, suggested in [2], [9], and [33]. The sequential-single placement consists in the sequential placement of the objects of   A  with respect to the   container   A 0   in a fixed order, say   A 1 , A 2 , . . . , A n , according to the special objective function. For instance, the valid position   p i   of   A i   must be a point with extremal (or specified) values of coordinates. (In case of planar problems   p i   = ( x i , y i )   can have, for example, a minimal, maximal, or specified   x i   and/or   y i .) The multiple (or simultaneous) placement, as follows from its name, is independent on the order of placement of the objects of   A   relative to   A 0 , and provides the placement of each object of   A , say   A j   , taking into account the possibility of the placement of all another objects   { A i } , where   1   ≤   i   ≤   n , and   i   6   =   j . The goal is to find the set   P 0 j   of all the feasible positions of   A j   , for   j   = 1 , . . . , n , with respect to   A 0 . The generalized sequential-single and multiple placement problems (i.e., the problems with more complex constraints on the relative position of objects than in [33] and [57]) and their solutions have been studied in [42].  9.3 Application to the other types of geometric situations  The work in [41] has studied the following types of geometric situations: The   translational   geometric situation   in direction   u   describes constraints on translational distances   in a given direction   between geometric objects. The minimum and maximum dis- tances   γ 1 , 2 ( B, A, u )   taking into account the   outer   position of   B   relative to   A   in direction   u   have been introduced in [22] and [37]. The minimum and maximum distances   η 1 , 2 ( B, A, u )   taking into account the   inner   position of   B   relative to   A   have been proposed in [39] and [41]. The parametric families of objects corresponding to the distances in a given direction are obtained 25
(a)   (b)  O y  A 2  x  B A 1  A 3  O y x  N V   ( B,   A )  A 3  A 1  A 2   B   +   p p  Figure 16: Illustration for the Problem V. (a) An objects   A   =   { A 1 , A 2 , A 3 }   and   B . (b) Here the region   N V   ( B,   A )   is siply connected,   A⊂ ( B   +   p ) , for   p   ∈   N V   ( B,   A ) ;   λ 1   = 0 ,   λ 2   <   0 , and  λ 3   =   λ 2 , respectively. Dashed lines show   ∂ ∆ 1 ( λ 1 − 3 , B, A ) . by using the   partial   vector operations on objects, which are generalizations of the Minkowski operations. See [41] and [45] for more detailes. The   rotational   geometric situation describes constraints on minimum and maximum   rota- tional   distances between geometric objects. Denote by   A ∗   the image of   A   in polar coordinates, i.e.,   A ∗   =   { ( r, θ )   |   ( r   cos   θ, r   sin   θ )   ∈   A } . Then a copy   A φ   of   A   rotated by an angle   φ   around the origin   O   corresponds to a copy   A ∗   +   { (0 , φ ) }   of   A ∗   translated by a point   (0 , φ )   in polar coordinates. Therefore one can use the   partial   vector operations in polar coordinates for mod- eling the relative position of geometric objects under rotations. The rotational distances and the translational distances in a given direction have used in [41] to formalize the constraints on the relative position of links in problems of modeling of mechanism’s motion. The   dynamic   geometric situation is defined, for moving objects, by representing an objects as a four-dimensional sets in the space-time   G 4 ; see [6], [39], and [41]. (Note that the distances between objects “in the space” and “in the time” are incomparable [64].) Let   A ∗   =   ⋃  t ∈ [0 , 1] [ A ( t )] ,   B ∗   =   ⋃  t ∈ [0 , 1] [ B ( t )]   be the image of   A, B   in   G 4 . We denote by   ⊕ t  the partial addition “by the time”, and by   ˇ B ∗   the reflection of   B ∗   with respect to the origin   O   in  R 3 . Let next   λK ∗   be the cylinder in   G 4   with a basis   λK . Then the parametric family of objects  Γ 1 ( λ, K, B ∗ , A ∗ ) =   ⋃  t ∈ [0 , 1]  [ A ( t ) ⊕   ˇ B ( t ) ⊕ λK ] =   A ∗   t  ⊕   ˇ B ∗   t  ⊕   λK ∗  corresponds to the distance   γ 1 ( B ∗ , A ∗ ) = inf t ∈ [0 , 1] { γ 1 [ B ( t ) , A ( t )] }   between   A ∗   and   B ∗ . It is clear that the suggested technique for solving the translational spatial planning problems can also be applied to geometric problems with the considered types of constaints on the relative position of objects.  10 Computational issues  From the observations of Sections 8 and 9 it follows that the C-space map of spatial plan- ning problem, is the region obtained by standard and/or regularized Boolean operations, and by 26
Minkowski operations on regular and/or non-regular objects. In general, the C-space map is a  non-regular   geometric object of various topology with   non-manifold   boundary; see Remark 5 of Section 8. (Recall that the non-regular object may have external dangling faces/edges and/or isolated points, and/or internal entities such as cracks and/or isolated points [43].) Therefore for implementation of spatial planning we need the methods for representation and manipu- lation of such an objects. In this section we briefly consider the computer representations of geometric objects that are suitable for solving the spatial planning problems, and the strategies for computing the C-space maps.  Representaions of geometric objects.   The two representation schemes that are most widely used in solid modeling and computer graphics are boundary representation (BRep) and con- structive solid geometry (CSG) [43].   Let   A   be a point set of   R n   ( n   = 2 ,   3 ).   CSG( A ) is a Boolean composition of algebraic halfspaces using regularized set operations. BRep( A ) is a collection of closed faces/edges. The problems of CSG to BRep conversion and of BRep to CSG conversion have been studied in [43], [50], and [51]. The third type of representation scheme suitable for our purpose is the linear ray represen- tation (LRRep) [31], [39], denoted by LRR( A ). (In [39] it is called the linear raster represen- tation.) LRR( A ) is an approximation of an object   A   by a set of parallel segments belonging to a grid   L   of parallel lines, i.e., LRR( A ) =   A   ∩   L . Conversions between BRep and LRRep, and between CSG and LRRep have been detally studied in [32]. The constructive non-regularized geometry (CNRG) methodology for representation and manipulation of non-homogeneous (i.e., made of several materials with different properties), non-closed point sets with internal structures and incomplete boundaries have been suggested in [48]. The work in [18] has proposed an approach for representation of geometric objects with non-manifold boundary. The boundary representation of non-regular geometric objects with non-manifold boundary using the techniques of [18] and [48] have been studied in [42]. It takes into account both the geometry and the topology of objects. The work in [42] have also considered the topological operations (complement, interior, closure, and regularization) on a single non-regular object.  Boolean operations.   Algorithms and implementation for computing the regularized set oper- ations on polyhedral objects have been proposed in [44]. Recall that the standard union   A   ∪   B  of two   r -sets   A   and   B   always results in an   r -set, whereas the standard intersection   A   ∩   B   and the standard set difference   A \ B   need not be regular: the set   A   ∩   B   may have dangling edges, e.g., in case where   A   contacts with   B   along the portion of its boundary [43]; the set   A \ B   may be partially open, e.g., in case where   i A   ∩   i B   6   =   ∅   [36], [44]. Algorithms for computing the set operations on non-manifold boundary representation objects have been proposed in [18] and [46]. We assume below some familiarity with theory and algorithms of [18] and [44]. As mentioned in [44], the algorithms will work with curved objects, and they are insensitive to whether a solid’s boundary is or is not a two-manifold, and is or is not connected. Hence, the algorithms of [44] can be modified to compute the standard Boolean operations on non-regular objects of various topology with non-manifold boundary. Let   S   =   A ⊗ ∗   B , where   ⊗   denotes one of the standard set operations. The main utilities used in algorithms of [44] to compute the boundary of   S   are the set membership classification (SMC) 27
[59], and the combining classifications, defined by means of the regularized set operations. See [44] and [59] for details. In [42] the algorithms of [44] have been modified for computing the standard Boolean set operations on non-regular (possibly unbounded) geometric objects of various topology, for BReps. To define and to combine the classifications the work in [42] have used the standard, but not a regularized set operations.  Minkowski operations.   Many various algorithms to compute the Minkowski operations have been proposed. Detailed surveys of previous work on computing the Minkowski operations can be found in [13], [20], [25], [26], [36], [60], and [63]. Algorithms for computing the Minkowski sums and the Minkowski differences in two and three dimensions are given, e.g., in [2], [3], [14], [15], [17], [25] – [29], [33], [37], and [60], for BReps, and in [31] and [39], for LRReps. Note that the referenced algorithms perform computing the Minkowski operations on regular objects. They can generate the manifold boundaries and are not applicable to the cases where the boundary of the resulting object is non-manifold; see [60] for details. In [12] and [20] have been presented an algorithms for   robust   and   efficient   construction of planar Minkowski sums for polygons using exact rational arithmetic.   In contrast with most existing techniques the algorithms of [12], [20] directly handle the degenerate configurations, arising in the boundary of the Minkowski sum, such as internal isolated points and/or coinciding edges.   In other words, these algorithms compute the outer envelope of   A   and   B , i.e., the boundary of the open set   i A ⊕ i B   (see subsection 2.1). The recent works in [61] and [62] have presented an algorithms for exact and efficient construction of Minkowski sums of polygons, and for exact and approximate construction of offset polygons, respectively, that handle the degenerate configurations also.   Hence, the algorithms of [12], [20], [61], and [62] allow to construct the parametric families of polygonal objects used for computing the C-space maps. The algorithms of [12] and [20] are based on convex decomposition of polygons. However, as mentioned in [3], not all curved objects permit convex decomposition, e.g., an object with an inward concave edge. Therefore to handle the curved objects more suitable are the methods that deal with the geometric objects directly. In [42] the algorithms of [3] have been modified for computing the Minkowski operations on non-regular objects of various topology, for BReps, using the techniques of [18] and [48].  Distances between geometric objects.   Many algorithms for computing the distances be- tween geometric objects have been developed (see [27]). Detailed surveys of previous work on computing the MTD between regular objects can be found in [10], [13], [16], [21], [27], and [35].   Algorithms for computing the distances concerning the outer relative position of objects in two and three dimensions (see subsection 2.2) are given, e.g., in [7], [10], [13] – [17], [35], [37], and [52], for BReps, and in [39] and [41], for LRReps.   The algorithms of [12], [20], and [61] for robust construction of planar Minkowski sums can be used for com- puting the MTD between non-regular polygonal objects. Algorithms for computing the distances concerning the containment of objects in two and three dimensions (see subsection 5.1) are given in [39] and [41], for LRReps. Note that for this goal can also be used algorithms for computing the Minkowski difference, for BReps; see, e.g., [14] and [15]. Algorithms for computing the distances concerning the covering of objects 28
(see subsection 5.2) and algorithms for computing the distances concerning the containment of objects are similar. Algorithms for computing the translational distances in a given direction in two and three dimensions are given in [10], [13], [22], and [52], for BReps, and in [39] and [41], for LR- Reps, respectively. The algorithms of [39] and [41] are based on the partial vector operations (see subsection 9.1). Algorithms for computing the rotational distances and the partial vector operations in polar coordinates are given in [41]. Thus, using the algorithms for computing the various types of distances between geometric objects provide solving the generalized distance query problem, as defined in subsection 1.3.  Acknowledgments  The author would like to thank Prof. Micha Sharir for his support, assistance, and advice on this work; for his useful suggestions in the content and presentation of this paper, and for helpful comments.  References  [1] Agarwal, P. K., Sharir, M., and Toledo, S., Applications of parametric searching in geomet- ric optimization, in   Proc. Third ACM-SIAM Symposium on Discrete Algorithms , 1992, pp. 72-82. [2] Avnaim, F. and Boissonnat J., Simultaneous containment of several polygons, in   Proc. Third ACM Symposium on Computational Geometry , 1987, pp. 242-250. [3] Bajaj, C. and Kim, M.-S., Generation of configuration space obstacles: The case of a mov- ing algebraic curves,   Algorithmica ,   4 , (2), 1989, pp. 157-172. [4] de Berg, M., van Kreveld, M., Overmars, M., and Schwartzkopf, O.,   Computational Geom- etry: Algorithms and Applications . Springer-Verlag, New York, 1997. [5] Buckley, C. E. and Leifer, L. J., A proximity metric for continuum path planning, in   Proc. 9th Int. Joint Conf. on Artificial Intelligence , 1985, pp. 1096-1102. [6] Cameron, S. A., A study of the clash detection problem in robotics, in   Proc. IEEE Int. Conf. on Robotics and Automation , 1985, pp. 488-493. [7] Cameron, S. A. and Culley, R. K., Determining the minimum translational distance between two convex polyhedra, in   Proc. IEEE Int. Conf. on Robotics and Automation , 1986, pp. 591- 596. [8] Chazelle, S., The polygon containment problem, in   Advances in Computing Research , vol- ume 1, Preparata, F. P., editor, pp. 1-33, JAI Press, Greenwich, CT, 1983. [9] Daniels, K. and Milenkovic, V., Multiple translational containment, Part I: An approximate algorithm,   Algorithmica ,   19 , (1-2), 1997, pp. 148-182. 29
[10] Dobkin, D. P., Hershberger, J., Kirkpatrick, D. G., and Suri, S., Computing the intersection depth of polyhedra,   Algorithmica ,   9 , 1993, pp. 518-533. [11] Elber, G. and Kim, M.-S., editors, Special issue: Offsets, sweeps and Minkowski sums,  Computer-Aided Design ,   31 , (4), 1999. [12] Flato, E. and Halperin, D., Robust and efficient construction of planar Minkowski sums, in   Proc. 16th European Workshop on Computational Geometry (EUROCG-2000) , 2000, pp. 85-88. [13] Fogel, E. and Halperin, D., Exact and efficient construction of Minkowski sums of convex polyhedra with applications, in   Proc. 8th Workshop on Algorithm Engineering and Experi- mentation (Alenex’06) , 2006. [14] Ghosh, P. K., A solution of polygon containment, spatial planning, and other related prob- lems using Minkowski operations,   Comput. Vision, Graphics and Image Process. ,   49 , 1991, pp. 1-35. [15] Ghosh, P. K., A unified computational framework for Minkowski operations,   Comput. Graphics ,   17 , (4) 1993, pp. 357-378. [16] Gilbert, E. G., Johnson, D. W., and Keerthi, S. S., A fast procedure for computing the distance between complex objects in three-dimensional space,   IEEE J. Robot. Automat. ,   4 , (2), 1988, pp. 193-203. [17] Guibas, L. J., Ramshaw, L., and Stolfi, J., A kinetic framework for computational geome- try, in   Proc. 24th Ann. IEEE Symp. Found. Comput. Sci.,   1983, pp. 100-111. [18] Gursoz, E. L., Choi, Y., and Prins, F. B., Boolean set operations on non-manifold boundary representation objects,   Computer Aided Design ,   23 , (1), 1991, pp. 33-39. [19] Hadwiger, G.,   Vorslesungen    ̈ u ber Inhalt, Oberfl  ̈ a che und Isoperimetrie , Shpringer-Verlag, Berlin, 1957. [20] Halperin, D., Robust geometric computing in motion,   Int. J. Robotics Res. ,   21 , (3), 2002, pp. 219-232. [21] Jimenez, P., Thomas, F., and Torras, C., 3D collision detection: a survey,   Computers and Graphics ,   25 , 2001, pp. 269-285. [22] Keerthi, S. S. and Sridharan, K., Efficient algorithms for computing two measures of depth of collision between convex polygons, Technical Report IISc-CSA-89-10, Indian Institute of Science, Bangalore, 1989. [23] Korn, G. A. and Korn, T. M.,   Mathematical Handbook for Scientists and Engineers , McGray-Hill, NY, 1968. [24] Latombe,   J.-C.,   Robot   Motion   Planning .   Kluger   Academic   Publishers, Boston/Dordrecht/London, 1991. 30
[25] Lee, I.-K., Kim, M.-S., and Elber, G., Polynomial/rational approximation of Minkowski sum boundary curves,   Graphical Models Image Process. ,   60 , (2), 1998, pp. 136-165. [26] Li, Z. and Milenkovic, V., Compaction and separation algorithms for nonconvex polygons and their applications,   European J. Oper. Res. ,   84 , (3), 1995, pp. 539-561. [27] Lin, M. C. and Manocha, D., Collision and proximity queries, in Goodman, J. E. and O’Rourke, J., editors,   Handbook of Discrete and Computational Geometry, 2nd Edition , chapter 35, pp. 787-807. CRC, 2004. [28] Lozano-Perez, T. and Wesley, M. A., An algorithm for planning collision-free paths among polyhedral obstacles,   Communications of the ACM ,   22 , (10), 1979, pp. 560-570. [29] Lozano-Perez, T., Spatial planning: A configuration space approach,   IEEE Trans. Com- put. ,   32 , (2), 1983, pp. 108-120. [30] Matheron, G.,   Random Sets and Integral Geometry , Wiley, New York, 1975. [31] Menon, J. P., Marisa, R. J., and Zagajac, J., More powerful solid modeling through ray representation,   IEEE Comput. Graphics Appl. ,   14 , (3), 1994, pp. 22-35. [32] Menon, J. P. and Voelcker, H. B., On the completeness and conversion of ray represen- tations of arbitrary solids, in   Proc. Third Symposium on Solid modeling and Applications , 1995, pp. 175-185. [33] Milenkovic, V., Multiple translational containment, Part II: Exact algorithms,   Algorith- mica ,   19 , (1-2), 1997, pp. 183-218. [34] Ong, C. J., Properties of penetration between general objects, in   Proc. IEEE Int. Conf. on Robotics and Automation , 1995, pp. 2293-2298. [35] Ong, C. J. and Gilbert, E. G., Grown distances: New measures for object separation and penetration,   IEEE Trans. Robot. Automat. ,   12 , (6), 1996, pp. 888-903. [36] O’Rourke, J.,   Computational Geometry in C , Cambrige University Press, Cambrige, 1994. [37] Popov, V. L.,   Development and Research of Methods and Algorithms for Geometric Mod- eling of Electrical Apparatus , Autor’s Abstract Cand. Tech. Sci. Dissertation, Kiev Polytech- nic Institute, 1982. In Russian. See also Popov, V. L., Mathematical methods of description and generating of constructions of electrical apparatus,   Electrical Industry , 8(75), 1978, pp. 3-6. In Russian. [38] Popov, V. L., Stoyan, Yu. G., and Gil’, N. I., Minkowski’s operations and the hodograph of the dense allocation function, Preprint, Institute for Problems in Machinery of Academy of Sciences of Ukranian SSR, Kharkov, 1977. In Russian. [39] Pustylnik, G. M., Mathematical methods and algorithms for geometric modeling of con- structions, Manuscript, 1983. In Russian. See also Pustylnik, G. M., The raster method of realization of geometric models on computer,   Mashines and Systems for Control , 1, 1986, pp. 110-112. In Russian. 31
[40] Pustylnik, G. M., Geometric modeling of relative position of figures and bodies and oper- ations of geometry of point sets. Manuscript, 1986. In Russian. [41] Pustylnik, G. M.,   Geometric Modeling of Mechanical Systems of Electrical Apparatus , Technical Report, Institute for Research and Development in Electrical Apparatus, Kharkov, 1987. In Russian. [42] Pustylnik, G. M., Spatial planning with constraints on translational distances between geometric objects. Manuscript, 2007.  http://www.cs.tau.ac.il/ ∼ genap/SpatPlan.ps ,  http://www.cs.tau.ac.il/ ∼ genap/SpatPlan.pdf . [43] Requicha, A. A. G., Representations for rigit solids: theory, methods and systems,   ACM Computing Syrveys ,   12 , (4), 1980, pp. 437-463. [44] Requicha, A. A. G. and Voelcker, H. B., Boolean operations in solid modeling: Boundary evaluation and merging algorithms,   Proceedings of the IEEE ,   73 , (1), 1985, pp. 30-44. [45] Rockafellar, R. T.,   Convex Analysis , Princeton, NY: Princeton Univ. Press, 1970. [46] Rossignac, J. R. and O’Connor, M. A., SGC: a dimension-independent model for pointsets with internal structures and incomplete boundaries, in Wozny, M., et al. (eds.)   Geometric Modeling for Product Ingineering: Proc. 1988 IFIP/NSF Workshop on Geometric Modeling , North-Holland, Amsterdam, 1989, pp. 145-180. [47] Rossignac, J. R. and Requicha, A. A. G., Offsetting operations in solid modelling,   Com- puter Aided Geometric Design ,   3 , (2), 1986, pp. 129-148. [48] Rossignac, J. R. and Requicha, A. A. G., Constructive non-regularized geometry,   Com- puter Aided Design ,   23 , (1), 1991, pp. 21-32. [49] Serra, J.,   Image Analysis and Mathematical Morphology , volume 1, Academic Press, New York, 1982. [50] Shapiro, V. and Vossler, D. L., Construction and optimization of CSG representations,  Computer-Aided Design ,   23 , (1), 1991, pp. 4-19. [51] Shapiro, V. and Vossler, D. L., Separation for boundary to CSG convertion,   ACM Trans- actions on Graphics ,   12 , (1), 1993, pp. 35-55. [52] Sridharan, K., Efficient computation of a measure of depth between convex objects for graphics applications,   Computers and Graphics ,   26 , 2002, pp. 785-793. [53] Stoyan, Yu. G.,   Placement of Geometric Objects , Naukova Dumka, Kiev, Ukraine, 1975. In Russian. [54] Stoyan, Yu. G., Mathematical methods for geometric design, in   Advances in CAD/CAM: Proc. of the 5th Int. Conf. PROLAMAT 82 , North-Holland, Amsterdam, 1983, pp. 67-86. See also Stoyan, Yu. G., On one generalization of the dense allocation function,   Reports Ukranian SSR Academy of Sciences , Ser.A 8, 1980, pp. 70-74. In Russian. 32
[55] Stoyan, Yu. G. and Ponomarenko, L. D., Minkowski’s sum and the hodograph of the dense allocation vector-function,   Reports Ukranian SSR Academy of Sciences , Ser.A, 10, 1977. In Russian. [56] Stoyan, Yu. G., Ponomarenko, L. D., and Vinarsky, V. Ya., Basic properties and methods of construction of   Φ -fuctions, Preprint, Institute for Problems in Machinery of Academy of Sciences of Ukranian SSR, Kharkov, 1984. In Russian. [57] Stoyan, Yu. G., and Yakovlev, S. V.,   Mathematical Models and Optimization Methods of Geometric Desing , Naukova Dumka, Kiev, 1986. In Russian. [58] Stoyan, Yu. G., and Yaskov, G. N., Mathematical model and solution method of optimiza- tion problem of placement of rectangles and circles taking into account special constraints,  Int. Trans. Oper. Res. ,   5 , (1), 1998, pp. 45-57. [59] Tilove, T., Set membership classification: A unified approach to geometric intersection problems,   IEEE Trans. Comput. ,   C-29 , (10), 1980, pp. 874-883. [60] Varadhan, G. and Manocha, D., Accurate Minkowski sum approximation of polyhedral models,   Graphical Models ,   68 , (3), 2006, pp. 343-355. [61] Wein, R., Exact and efficient construction of planar Minkowski sums using the convolution method, in   Proc. 14th Annual European Symposium on Algorithms (ESA) , Zurich, September 2006. [62] Wein, R., Exact and approximate construction of offset polygons,   Computer-Aided Design  (2007), doi:10.1016/j.cad2007.01.010 [63] Wise, K. D. and Bowyer, A., A survey of global configuration-space mapping techniques for a single robot in a static inviroment,   Int. J. Robot. Res. ,   19 , (8), 2000, pp. 762-779. [64] Yaglom, I. M.,   Galilei’s Principle of Relativity and Non-Euclidean Geometry , Nauka, Moscow, 1969. In Russian. 33