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 Rn, for n = 2 or 3, i.e.,
bounded, closed, and semi-analytic subsets of Rn [43]. This means that, for any r-set A of
Rn, 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 Ac 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 Rn are defined as A ⊗∗B = ki(A ⊗B), where ⊗∈{∪, ∩, \}; see [43] and [44] for
details. The regularized complement Ac∗of A is defined as Ac∗= ki(Ac). 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]):
d1(B, A) = inf
a∈A inf
b∈B ∥a −b∥;
d2(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∗∈Ac 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 Rn.
These distances between r-sets have the following basic properties [19]:
d1(A, B) > 0 ⇐⇒A ∩B = ∅; d2(A, A) = diam(A); H(A, B) = 0 ⇐⇒A = B.
Clearly, d∗(A, B) = d1(Ac, 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) =
n
d1(B + p, A) ≤λ1

⊙1

d1(B + p, A) ≥λ2
o
⊙2
n
d2(B + p, A) ≤λ3

⊙1

d2(B + p, A) ≥λ4
o
⊙2
n
d∗(B + p, A) ≤λ5

⊙1

d∗(B + p, A) ≥λ6
o
,
where ⊙1(2) ∈{∨, ∧}, find the region NI(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) = (Ac⊕B)c,
respectively [30], [49]. See Figure 1(a). The Minkowski subtraction is a dual operation of the
Minkowski addition. Note that A⊕B = (Ac⊖B)c.
(b)
(a)
O
x
x
O
B
ˇ
B
p1
B + p3
y
y
A ⊖ˇ
B
p3
A ⊖B
B + p1
A⊕ˇ
B
A
A⊕B
A
p2
B + p2
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 p1 ∈∂(A⊕ˇB), p2 ∈∂(iA⊕i ˇB), (B + p1,2) ˙∩A,
and p3 ∈∂(A ⊖ˇB), (B + p3) ˙⊂A, respectively. (Dashed lines show an objects B + p, where
(a) p ∈∂A, (b) p ∈∂(iA⊕i ˇB) (resp., p ∈∂(A ⊖ˇB)). Dotted lines show pieces of ∂(iA⊕iB)
(resp., ∂(iA⊕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) = (Ac⊕ˇ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 ̸= ∅
⇐⇒p ∈A⊕ˇB;
(B + p) ∩A = ∅
⇐⇒p ∈(A⊕ˇB)c;
(B + p) ˙∩A
⇐⇒p ∈∂(iA⊕i ˇB),
(1)
where B ˙∩A = [(iA ∩iB = ∅) ∧(∂A ∩∂B ̸= ∅)] 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
∂(iA⊕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)⊆∂(iA⊕i ˇB), and that the set ∂(iA⊕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) = ∂(Ac⊕i ˇB) and A⊖(−(B +p)) = (A⊖ˇB)−p, it follows
that if A⊖ˇB ̸= ∅, we get (see [30] and [39]):
(B + p)⊂A
⇐⇒p ∈A⊖ˇB;
(B + p) ̸⊂A
⇐⇒p ∈(A⊖ˇB)c;
(B + p) ˙⊂A
⇐⇒p ∈∂(A⊖ˇB),
(2)
where B ˙⊂A = [(Ac ∩iB = ∅) ∧(∂A ∩∂B ̸= ∅)] denotes the inner touching of A and B. See
Figure 1(b).
By observations of [3] and [31] we have (iA⊕iB)⊆i(A⊕B); (iA⊖iB)⊇i(A⊖B) and
∂(A⊕B)⊆∂(iA⊕iB); ∂(A⊖B) = ∂(iA⊖iB) = ∂(Ac⊕iB);
A⊕B = (iA⊕iB) ∪∂(iA⊕iB); A⊖B = i(A⊖B) ∪∂(A⊖B);
(3)
(A⊕B)c = (iA⊕iB)c\∂(iA⊕iB); (A⊖B)c = k[(A⊖B)c]\∂(A⊖B).
(4)
From the observations of [19] it follows that, for r-sets, we have
A⊕iB = iA⊕B = iA⊕iB; A⊕B = k(iA⊕iB); A⊖B = A⊖iB = iA⊖iB.
(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⊕ˇBc, and then A ∩(Bc + 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 ̸⊂(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 ̸= ∅
⇐⇒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 d1(B, A) does not take into account the “amount” of intersec-
tion between objects A and B, since d1(B, A) = 0, for A ∩B ̸= ∅, 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 MTD(A, B), introduced in [7], is defined as
MTD(A, B) =
 −MTD+(A, B),
for A ∩B ̸= ∅;
MTD+(A, B),
otherwise,
where MTD+(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) =



infc∈∂(A⊕ˇB) ∥c∥,
for A ∩B = ∅;
0,
for A ˙∩B;
−infc∈∂(A⊕ˇB) ∥c∥,
for A ∩B ̸= ∅,
γ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) = ∂(iA⊕i ˇB) (see subsection 2.1). Then, in general, we obtain that
γ1(B, A) =

infc∈∂(iA⊕i ˇB) ∥c∥,
for A ∩B = ∅;
−infc∈∂(iA⊕i ˇB) ∥c∥,
otherwise.
See Figure 3. By the observations of subsection 2.1, we get γ1(B, A) = γ1(O, iA⊕i ˇB), and
γ1(B, A)



< 0,
for O ∈iA⊕i ˇB;
= 0,
for O ∈∂(iA⊕i ˇB);
> 0,
for O ∈(A⊕ˇB)c.
Note that in the above relationships the set iA (resp., i ˇB) can be replaced by A (resp., ˇB), since
iA⊕i ˇB = A⊕i ˇB = iA⊕ˇB, for r-sets. See [42] for more details.
It can easily be shown that γ1(B, A) = MTD(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) = ∂(iA⊕i ˇB). Here (a) A ∩B ̸= ∅, (b) A ˙∩B, and (c) A ∩B = ∅, respectively.
(a)
(b)
(c)
x
y
x
y
O
γ1(B, A) = 0
O
py
y
px
A
A
B
A
B
B
γ1(O, iA⊕i ˇ
B)
∂(iA⊕i ˇ
B)
∂(iA⊕i ˇ
B)
∂(iA⊕i ˇ
B)
O
γ1(O, iA⊕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)⊂∂(iA⊕i ˇB). Here (a) A ∩B ̸= ∅; px, py 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) = d1(B, A), for A ∩B = ∅, and γ2(B, A) = γ2(O, A⊕ˇB) = d2(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) = ∂(iA⊕i ˇB⊕iλK), for λ > 0, and ∂(A⊕ˇB) = ∂(iA⊕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 −rA ≤λ ≤0,
where rA 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(−rA, 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(−rA, K, A)⊂A.
A second parametric family of objects
Γ2(λ, K, A) = λK⊖A, for λ ≥RA,
where RA 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 λ < −rA, and Γ2(λ, K, A) = ∅if and only if λ < RA. 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(RA, 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(RA, 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 λ ≥RA. (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
λ = RA
Γ2(λ, K, A)
λ = −rA
Figure 4: The parametric families of objects Γ1,2(λ, K, A), for various values of λ, and the
distances γ1,2(p, A). Here Γ2(RA, K, A) ̸∈A, dashed curves show ∂Γ1,2(λ, K, A), and the
dotted line shows a piece of ∂Γ1(λ, K, iA). The objects Γ1(−rA, K, A) and Γ2(RA, 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) =



infa∈∂A ∥p −a∥,
for p ∈Ac;
0,
for p ∈∂A;
−infa∈∂A ∥p −a∥,
for p ∈iA,
γ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, iA);
= λ, for p ∈∂Γ1(λ, K, iA);
> λ, for p ∈[Γ1(λ, K, A)]c,
γ1(p, A)



≤λ, for p ∈Γ1(λ, K, A);
̸= λ, for p ∈[∂Γ1(λ, K, iA)]c;
≥λ, for p ∈[Γ1(λ, K, iA)]c.
(b) For −rA ≤λ ≤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);
̸= λ, for p ∈[∂Γ1(λ, K, A)]c;
≥λ, for p ∈k[Γ1(λ, K, A)]c.
Observation 2 For λ ≥RA 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);
̸= λ, for p ∈[∂Γ2(λ, K, A)]c;
≥λ, for p ∈k[Γ2(λ, K, A)]c.
It is clear that infp∈Rn{γ1(2)(p, A)} = −rA(RA). 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) = 2RA, it can easily be shown that γ2(p, A) = diam({p} ∪A) > λ if
and only if p ∈[Γ2(λ, K, A)]c, for λ ≥2RA. Then we get diam({O} ∪A) ∼Γ2(λ, K, A), for
λ ≥2RA. (Note that γ2(p, A) ≤diam({p}∪A) = diam(A) = λ if and only if p ∈Γ2(λ, K, A),
for λ ≤2RA.)
The properties of the distances γ1,2(p, A) and their corresponding families Γ1,2(λ, K, A) in
case where A = Sn
j=1 Aj and/or A = Tn
j=1 Aj, for A ̸= ∅, 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, iA⊕i ˇB), for i = 1, 2. (b) γi(p, iA⊕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, (iA⊕i ˇB)θ], for i = 1, 2.
Remark 1 For i = 2, the sets iA and/or iB can be replaced by A and/or B, respec-
tively, since sup{∥c∥| c ∈∂(iA⊕i ˇB)} = sup{∥c∥| c ∈∂(A⊕ˇB)}, i.e., γ2(p, iA⊕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, iA} and B∗∈{B, iB}, respectively.
Let us first consider the parametric family of objects
Γ1(λ, K, B, A) =
 (A⊕ˇB)⊕λK,
for λ ≥0;
(A⊕ˇB)⊖|λ|K,
for −rA⊕ˇB ≤λ ≤0,
(see Figure 5(a)). Since Γ1(λ, K, B, A) = Γ1(λ, K, A⊕ˇB), the object Γ1(−rA⊕ˇ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, iA);
= λ, for p ∈∂Γ1(λ, K, B, iA);
≥λ, for p ∈[Γ1(λ, K, B, iA)]c.
(b) For −riA⊕i ˇB ≤λ < 0 we have
γ1(B + p, A)







≤λ, for p ∈Γ1(λ, iK, iB, iA);
< λ, for p ∈iΓ1(λ, iK, iB, iA);
= λ, for p ∈∂Γ1(λ, iK, iB, iA);
≥λ, for p ∈k[Γ1(λ, iK, iB, iA)]c.
See Figures 5(a) and 6(a). Hence, the set
P(λ, K, B, A) =

p | γ1(B + p, A) = λ
	
=

∂Γ1(λ, K, B, iA) for λ ≥0;
∂Γ1(λ, iK, iB, iA), for −riA⊕i ˇB ≤λ < 0,
is the surface of the function γ1(B + p, A), and infp∈Rn{γ1(B + p, A)} = −riA⊕i ˇB. Thus, we
get
10
Theorem 6 γ1(B, A) ∼
 Γ1(λ, K, B, A), for λ ≥0;
Γ1(λ, iK, iB, iA), for −riA⊕i ˇB ≤λ < 0.
Note that in case where λ ≥0 the Theorem 6 has also been proved in [37] and [56].
Denote by dP(A, B) the penetration depth of A and B (see [35]). In [42] it is shown that
γ1(B, A) = −dP(iA, iB), for A ∩B ̸= ∅. Then we have dP(A, B) ∼Γ1(λ, K, B, A), for
−rA⊕ˇB ≤λ < 0.
Let us next consider the parametric family of objects
Γ2(λ, K, B, A) = λK⊖(A⊕ˇB), for λ ≥RA⊕ˇ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(RA⊕ˇ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, iA), and γ1(B + q, A) = λ1, for q ∈∂Γ1(λ1, K, B, iA).
Observation 7 For λ ≥RA⊕ˇ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, infp∈Rn{γ2(B + p, A)} = RA⊕ˇB.) Then we get the following:
Theorem 8 γ2(B, A) ∼Γ2(λ, K, B, A), for λ ≥RA⊕ˇ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 λ ≥2RA⊕ˇB. Hence, diam(B ∪A) ∼Γ2(λ, K, B, A), for
λ ≥2RA⊕ˇ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, iK, iB, iA)
B
B
γ1(B + p, A)
p
B + p
∂(iA⊕i ˇ
B)
∂(iA⊕i ˇ
B)
A
Figure 6: The objects (a) Γ1(λ1, iK, iB, iA) and (b) Γ2(λ2, K, B, A). Here γ1,2(B+p, A) = λ1,2
and λ1 < 0. A dashed lines show ∂(iA⊕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) =



infc∈∂(A⊖ˇB) ∥c∥,
for B ̸⊂A;
0,
for B ˙⊂A;
−infc∈∂(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 ̸= ∅.)
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) = ∂(Ac⊕i ˇB), we have
η1(B, A) = −γ1(B, Ac) 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 ̸⊂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]:
H1(λ, K, B, A) =

(A⊖ˇB)⊕λK,
for λ ≥0;
(A⊖ˇB)⊖|λ|K,
for −rA⊖ˇB ≤λ ≤0,
H2(λ, K, B, A) =
λK⊖(A⊖ˇB),
for λ ≥RA⊖ˇB,
See Figure 8.
(a)
(b)
A
x
η1(B + p, A)
A
x
y
y
p
B
B
B + p
H1(λ1, K, B, A)
B + p
H2(λ2, K, B, A)
∂(A ⊖ˇ
B)
∂(A ⊖ˇ
B)
p
η2(B + p, A)
Figure 8: The objects H1,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 ∈H1(λ, K, B, A);
< λ, for p ∈H1(λ, iK, B, A);
= λ, for p ∈∂H1(λ, iK, B, A);
≥λ, for p ∈[H1(λ, iK, B, A)]c.
(b) For i = 1, 2, −rA⊖ˇB ≤λ1 ≤0, and λ2 ≥RA⊖ˇB, respectively, we have
ηi(B + p, A)







≤λi, for p ∈Hi(λi, K, B, A);
< λi, for p ∈iHi(λi, K, B, A);
= λi, for p ∈∂Hi(λi, K, B, A);
≥λi, for p ∈k[Hi(λi, K, B, A)]c.
Then infp∈Rn{η1(2)(B + p, A)} = −rA⊖ˇB(RA⊖ˇB). Thus, by above, we obtain the following:
Theorem 11 ηi(B, A) ∼Hi(λ, K, B, A), for i = 1, 2.
The additional properties of the distances η1,2(B, A) and the families H1,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) =



infc∈∂( ˇB⊖A) ∥c∥,
for A ̸⊂B;
0,
for A ˙⊂B;
−infc∈∂( ˇ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 ̸= ∅.)
(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 ̸⊂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(Bc, 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) = −Hi(λ, 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(λ, iK, B, A);
= λ, for p ∈∂∆1(λ, iK, B, A);
≥λ, for p ∈[∆1(λ, iK, 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, infp∈Rn{δ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) = supb∈B{γ1(b, A)}, eliminating
this shortcoming, and it is shown that
µ(B, A) =
 h(B, A), for B ̸⊂A;
η1(B, A), otherwise.
Then the signed distance µ(A, B) can be defined as
µ(A, B) =

h(A, B), for A ̸⊂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 M1(λ, K, B, A) =
Γ1(λ, A)⊖ˇB, for λ ≥−rA⊖ˇB, and it is shown that µ(B, A) ∼M1(λ, K, B, A); see Fig-
ure 11(a). The family of objects M2(λ, 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) ∼M2(λ, K, B, A), and H(A, B) ∼
M3(λ, K, B, A) = [M1(λ, K, B, A)∩M2(λ, K, B, A)], respectively. See Figure 11(b). Clearly,
for −r ˇB⊖A ≤λ ≤0, we have µ(A, B) ∼M2(λ, K, B, A).
For notational convenience, the distances µ(B, A), µ(A, B), and H(A, B) are sometimes
denoted by m1(B, A), m2(B, A), and m3(B, A), respectively. Then we get
Theorem 15 mi(B, A) ∼Mi(λ, K, B, A), for i = 1 −3.
The objects M1−3(λ, K, B, A) have the following simple properties:
M1(2)(λ, K, B, A) = −M2(1)(λ, K, A, B); M3(λ, K, B, A) = −M3(λ, K, A, B).
Observation 16 (a) For i = 1 −3, and λ > 0 we have
mi(B + p, A)







≤λ, for p ∈Mi(λ, K, B, A);
< λ, for p ∈iMi(λ, iK, iB, iA);
= λ, for p ∈Mi(λ, K, B, A)\iMi(λ, iK, iB, iA);
≥λ, for p ∈k[M1(λ, iK, iB, iA)]c.
16
(a)
(b)
y
A
p
x
B
y
x
p
A
B + p
µ(B + p, A)
µ(A, B + p)
ˇ
B
∂(A ⊖ˇ
B)
M2(λ2, K, B, A)
B + p
M1(λ1, K, B, A)
∂Γ1(λ1, K, A)
Figure 11: The objects (a) M1,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, iK, iA), ∂Γ1(λ2, K, ˇB) =
∂Γ1(λ2, iK, i ˇB).
(b) For i = 1, 2, −rA⊖ˇB ≤λ1 ≤0, and −r ˇB⊖A ≤λ2 ≤0 we have
mi(B + p, A)







≤λi, for p ∈Mi(λi, K, B, A);
< λi, for p ∈iMi(λi, K, B, A);
= λi, for p ∈∂Mi(λi, K, B, A);
≥λi, for p ∈k[Mi(λ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), m1−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 ̸⊂A)
⇐⇒

γ1(B, A) > 0
 V n
η1(B, A) > 0
 W 
µ(B, A) > 0
o
;
(A ∩B ̸= ∅) ∧(A⊂B)
⇐⇒

γ1(B, A) ≤0
 V n
δ1(B, A) ≤0
 W 
µ(A, B) ≤0
o
.
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 AT 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) ̸= λ] = [ω(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 ⊙∈{<, ≤, =, ̸=, ≥, >}, 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) ̸= λ], 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) ̸= λ];
[ω(B + p, A) = λ] = [ω(B + p, A) ≤λ] ∧[ω(B + p, A) ≥λ];
[ω(B + p, A) > λ] = [ω(B + p, A) ≥λ] ∧[ω(B + p, A) ̸= λ].
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 ∈N1(B, A) = Ω(λ1, K, B, A);
ν2(B + p, A) = [ω(B + p, A) > λ2]
⇐⇒p ∈N2(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) = N1(B, A) ∩N2(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) = N1(B, A) ∪N2(B, A). If λ1 ≥λ2 then N(B, A) = Rn. (Note that in this case
ν(B + p, A) ̸= 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) = Wn
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[N1(B, A), . . . , Nk(B, A)] if (but not only if) νi(B+p, A) ∼Ni(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 Ni(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) = Rn.
The region N(B, A) is called the solution of the TGS ν(B + p, A). (Note that the region
Ni(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 Nl(B, A), denoted by νl, Nl,
for short. Denote also ω(B + p, A), Ω(λ, K, B, A) by ω, Ω(λ). Below we let i(j) = 1, 2.
1 ν1 = (γi ≤λi) ∧(γj ≥λj);
N1 = Γi(λi) ∩k[Γj(λj)]c = Γi(λi)\iΓj(λj).
1a ν1a = (γi < λi) ∧(γj > λj);
N1a = iΓi(λi) ∩[Γj(λj)]c = iΓi(λi)\Γj(λj).
1b ν1b = (γi ≤λi) ∧(γj > λj);
N1b = Γi(λi) ∩[Γj(λj)]c = Γi(λi)\Γj(λj).
1c ν1c = (γi ≥λi) ∧(γj ≥λj);
N1c = k[Γi(λi)]c ∩k[Γj(λj)]c = k[Γi(λi) ∪Γj(λj)]c.
2 ν2 = (γi = λi) ∧(γj = λj);
N2 = ∂Γi(λi) ∩∂Γj(λj).
3 ν3 = (γ1 ≥λ1) ∧(γ2 →min), where λ1 ̸= r(A⊕ˇB);
N3 = k[Γ1(λ1)]c ∩Γ2(RA⊕ˇB) = Γ2(RA⊕ˇB)\iΓ1(λ1).
4 ν4 = (η1 →min);
N4 = H1(−rA⊖ˇB).
5 ν5 = (η1 ≤λ1 ≤0) ∧(η2 →min);
N5 = H1(λ1) ∩H2(RA⊖ˇB).
6 ν6 = [(γ1 = λ1) ∧(γ2 = λmin)] ̸= 0;
N6 = ∂Γ1(λ1) ∩∂Γ2(λmin),
where λmin =
 inf{λ | Γ2(λ) ˙⊂Γ1(λ1)}, for Γ2(RA⊕ˇB) ∈Γ1(λ1);
inf{λ | Γ2(λ) ˙∩Γ1(λ1)}, for Γ2(RA⊕ˇ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 N1 is closed bounded, whereas the region N1a is open bounded; the region N1c 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
N1b give an example of such an object. In case where i = j, λi > λj, and λi,j > 0, respectively,
the object N1 is regular, i.e.,N1 = Γi(λi)\∗Γj(λj). (Note that in case where λi = λj we get
N1 = ∂Γi(λi), i.e., the object N1 is non-regular.)
20
A
∂(A⊕ˇ
B)
B
O
x
x
A
∂(A ⊖ˇ
B)
∂Γ2(λ2)
∂Γ1(λ1)
∂Γ2(λmin)
p1
p2
N1
N4
N3
q1
q3
q2
y
y
Figure 12: The corresponding regions Nl of TGS’s νl, for l = 1, . . . , 6, in case where
Γ2(RA⊕ˇB) ̸∈Γ1(λ1). Here i = 2, j = 1, and λ1 < λ2, respectively. The region N1 is
simply connected, N2 = {p1, p2}, and N3 = Γ2(RA⊕ˇB), respectively. The region N4 is a curve,
N5 = ∅, and N6 = {q1, q2, q3}.
Let us next consider the following problem:
Problem II Find the region NII, 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
NII =
n
Γ1(λ2)\iΓ1(λ1)

∩

Γ2(λ4)\iΓ2(λ3)
o
∪
n
H1(λ6)\iH1(λ5)

∩

H2(λ8)\iH2(λ7)
o
.
See Figure 13. Note that in case where λ1 > λ2 or λ3 > λ4, and λ5 > λ6 or λ7 > λ8 we have
NII = ∅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)

∪

H1(λ5)\iH1(λ6)

;
N′′
I =

Γ1(λ1) ∪k[Γ1(λ2)]c
∩[Γ2(λ3) ∪k[Γ2(λ4)]c
∩

H1(λ5) ∪k[H1(λ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 = Rd. (However, ν′′
I ̸= 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
NII
NII
Figure 13: Illustration for the Problem II. Here the region NII is 5-connected.
9.1 Findspace problem
Let A = {A1, . . . , An} be a collection of n, possibly intersecting, obstacles Ai, 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 = Sn
i=1 Ai.)
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 COB(A) = {p | (B + p) ∩A ̸=
∅} = A⊕ˇB = Sn
i=1 COB(Ai) = Sn
i=1(Ai⊕ˇB) [29]. (The object [COB(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 CIB(R) = {p | (B + p)⊆R} = [COB(Rc)]c; see Figure 14(a). By the definition of the
Minkowski difference, we get CIB(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 FPB(A, R) = (R\A)⊖ˇB = (R⊖ˇB)\(A⊕ˇB) = CIB(R)\COB(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] = Vn
i=1[γ1(B + p, Ai) > 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) =
h
η1(B + p, R) ≤0
i ^  n^
i=1
h
γ1(B + p, Ai) > 0
i
.
22
(a)
(b)
B
x
y
A1
A2
A3
R
∂[CIB(R)]
x
O
y
A3
A1
A2
R
NIII(B, A, R)
F PB(A, R)
p1
B + p1
p2
B + p2
Figure 14: The translational Findspace problem in case where A = {A1, A2, A3}. (a) Here
the region FPB(A, R) is connected, and p1,2 are the free positions of B.
Dashed lines
show ∂[COB(A)] and ∂[CIB(R)], respectively.
(b) Illustration for the Problem III. Here
NIII(B, A, R) is a two-connected region and λ1 = 0, λ2 = |λR|, and λ3 = 1.5·λ2, respectively.
Dashed curves show ∂[COB(λA, A)] and ∂[CIB(λR, R)].
Since [γ1(B + p, Ai) > 0] = [γ1(B + p, Ai) ≤0]c, we have Vn
i=1

γ1(B + p, Ai) > 0

=
 Wn
i=1[γ1(B + p, Ai) ≤0]
	c. Hence, the solving of the Findspace problem can be represented
as follows:
N(B, A, R) = H1(0, K, B, R)
\ n\
i=1
h
Γ1(0, K, B, Ai)
ic
= H1(0, K, B, R)
\ h n[
i=1
Γ1(0, K, B, Ai)
ic
= H1(0, K, B, R)
\
Γ1

0, K, B,
n[
i=1
Ai
c
= H1(0, K, B, R)

Γ1(0, K, B, A).
Clearly, H1(0, K, B, R) = CIB(R) and Γ1(0, K, B, A) = COB(A).
We next consider more general Findspace problems.
Problem III Find the corresponding region NIII(B, A, R) of the TGS
νIII(B + p, A, R) =
h
η1(B + p, R) ≤λR ≤0
i ^  n^
i=1
h
γ1(B + p, Ai) > λi ≥0
i
.
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 Wn
i=1[γ1(B + p, Ai) ≤λi], and therefore it can be
represented as COB(λA, A) = Sn
i=1 Γ1(λi, K, B, Ai). The interior C-space corresponding to
23
the TGS [η1(B +p, R) ≤λR ≤0] is the region CIB(λR, R) = H1(λR, K, B, R). (See Sections
4, 5, and Figure 14(b).) Thus, we get
NIII(B, A, R) = H1(λR, K, B, R)
\ n\
i=1
h
Γ1(λi, K, B, Ai)
ic
= H1(λR, K, B, R)
h n[
i=1
Γ1(λi, K, B, Ai)
i
.
Problem IV Find the solution NIV (B, A) of the TGS
νIV (B+p, A) =
h
γl1(B+p, A) ≤λ1
i ^ h
γl2(B+p, A) > λ2
i
, where l1(2) = 1, 2; λ1(2) ≥0.
Solving the Problem IV. The general solution is the region
NIV (B, A) = Γl1(λ1, K, B, A)
\h
Γl2(λ2, K, B, A)
ic
= Γl1(λ1, K, B, A)\Γl2(λ2, K, B, A).
By observations of [42] and of Section 8, in case where l1(2) = 1 and λ1(2) ≥0, we have
νIV (B + p, A) =
 n_
i=1
h
γ1(B + p, Ai) ≤λ1
i ^  n^
i=1
h
γ1(B + p, Ai) > λ2
i
;
NIV (B, A) =
h n[
i=1
Γ1(λ1, K, B, Ai)
ih n[
i=1
Γ1(λ2, K, B, Ai)
i
,
whereas, for l1(2) = 2 and λ1(2) ≥min1≤i≤n{RAi⊕ˇB}, we get
νIV (B + p, A) =
 n^
i=1
h
γ2(B + p, Ai) ≤λ1
i ^  n_
i=1
h
γ2(B + p, Ai) > λ2
i
;
NIV (B, A) =
h n\
i=1
Γ2(λ1, K, B, Ai)
ih n\
i=1
Γ2(λ2, K, B, Ai)
i
.
See Figure 15. Note that νIV (B + p, A) = 0 and NIV (B, A) = ∅, for λ1 ≤λ2.
Finally, we consider the Findspace problem concerning the covering of objects.
Problem V Find the region NV (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
h
δ2(B + p, Ai) ≤εi
i ^  n^
i=1
h
λ−
i ≤δ1(B + p, Ai) ≤λ+
i ≤0
i
.
The solution is
NV (B + p, A) =
h n[
i=1
∆2(εi, K, B, Ai)
i \  n\
i=1
h
∆1(λ+
i , K, B, Ai)

i∆1(λ−
i , K, B, Ai)
i
.
For more simple constraint νV (B +p, A) = Vn
i=1[δ1(B +p, Ai) ≤λi ≤0], we get NV (B, A) =
Tn
i=1 ∆1(λi, K, B, Ai); see Figure 16.
24
(a)
(b)
x
O
O
NIV (B, A)
A1
A2
A1
A2
x
y
y
NIV (B, A)
Figure 15: Illustration for the Problem IV. Here A = {A1, A2}, both A1 and A2 are line seg-
ments, B = {O}, λ1 > λ2, and the region NIV (B, A) is connected. Dashed curves show pieces
of ∂Γl1(l2)(λ1(2), B, A1(2)). Here (a) l1(2) = 1, and (b) l1(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 A0 in a fixed order, say A1, A2, . . . , An, according to the special
objective function. For instance, the valid position pi of Ai must be a point with extremal (or
specified) values of coordinates. (In case of planar problems pi = (xi, yi) can have, for example,
a minimal, maximal, or specified xi and/or yi.)
The multiple (or simultaneous) placement, as follows from its name, is independent on the
order of placement of the objects of A relative to A0, and provides the placement of each object
of A, say Aj, taking into account the possibility of the placement of all another objects {Ai},
where 1 ≤i ≤n, and i ̸= j. The goal is to find the set P0j of all the feasible positions of Aj,
for j = 1, . . . , n, with respect to A0.
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
A2
x
B
A1
A3
O
y
x
NV (B, A)
A3
A1
A2
B + p
p
Figure 16: Illustration for the Problem V. (a) An objects A = {A1, A2, A3} and B. (b) Here
the region NV (B, A) is siply connected, A⊂(B + p), for p ∈NV (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 G4; see [6], [39], and [41]. (Note that the distances
between objects “in the space” and “in the time” are incomparable [64].)
Let A∗= S
t∈[0,1][A(t)], B∗= S
t∈[0,1][B(t)] be the image of A, B in G4. We denote by ⊕t
the partial addition “by the time”, and by ˇB∗the reflection of B∗with respect to the origin O in
R3. Let next λK∗be the cylinder in G4 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∗) = inft∈[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 Rn (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 iA ∩iB ̸= ∅[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 iA⊕iB (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 ¨uber Inhalt, Oberfl¨ache 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