# Symbolic Computation of the Orthogonal Projection of Rational Curves onto Rational Parameterized Surfaces

Authors: Zhiwang Gan; Meng Zhou
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper focuses on the orthogonal projection of rational curves onto rational parameterized surface. Three symbolic algorithms are developed and studied. One of them, based on regular systems, is able to compute the exact parametric loci of projection. The one based on Gröbner basis can compute the minimal variety that contains the parametric loci. The remaining one computes a variety that contains the parametric loci via resultant. Examples show that our algorithms are efficient and valuable.


---

## Body

## 1. Introduction

Computing the projection of a point onto a surface is to find a closest point on the surface, and projection of a curve onto a surface is the locus of all points on the curve project onto the surface. The orthogonal projection problem attracted great interest in minimal distance computation [1, 2], calculating the intersection of curves and surfaces [3], surface curve design [4, 5], curve or surface selecting [6], and shape registration [7]. And many algorithms have been developed. The work in [8] proposed a second-order tracing method for calculating the orthogonal projection of parametric curves onto B-spline surfaces. The work in [9] focused on projecting points onto conics. The work in [10] developed a second-order algorithm for orthogonal projection onto curves and surfaces. The work in [11] used a torus patch to approach the surface in projection computation. In [12], an efficient algorithm is presented for projecting a point to its closest point. Among these methods, the common steps are to find the approach projective point in normed space by iteration techniques which rely on good initial values and then determine the approximate parameters in parametric space, which is called apoint inversion problem.Numerical methods above are efficient and stable in computing orthogonal projection and are easy applied. However, there exist common drawbacks as follows: the computation relies on samplings and the step size determines the accuracy of the result. The projective locus might be invisible while the locus is smaller than the step size. And the curve is always assumed to keep close enough to the surface so that a single solution is guaranteed. Symbolic methods would be necessary to overcome the shortcomings. Previous applications of symbolic methods in CAGD could be seen in [13–15]. In order to apply symbolic methods, we only are concerned about curves and surfaces that have rational parametric representations. As known to all, common representations of surface and curves are NURBS [16], which is formed by rational patches. And since the parametric locus could uniquely determine the projection in 3D space, we focus on the parametric locus of orthogonal projection. Moreover, the range of surfaces and curves is restricted in R
3.Classical symbolic tools applied in this paper are regular systems [17] (triangular decomposition), Gröbner basis [18], and resultant (see [19, 20]). Parametrization of curves and surfaces is a hard task in the area [21]. But, for convenience, we only consider parametric curves and surfaces. With the rational assumptions of curves and surfaces, the orthogonal condition would be transformed into a simple polynomial system. Then the orthogonal projection problem equals determining the real solution of the polynomial system, which can be solved by symbolic or mix symbolic-numeric techniques.In this paper, three algorithms are presented to compute the orthogonal projection of a rational parameterized curve onto a rational parameterized surface. The algorithm based on regular systems is able to compute the exact loci of orthogonal projection, and the false points will be detected. By means of Gröbner bases, we can get the minimal variety that contains the projective loci. And the resultant method efficiently computes a variety that contains the projective loci. The former two algorithms can particularly be used to compute point projections.Compared with numerical algorithms, our algorithms have distinct advantages:(1)
We generate the exact results without numerical errors.
(2)
Both point projection and curve projection are included.
(3)
There is no point inversion problem involved since we directly are concerned about the parametric loci.In addition, the decomposition method in [22] would generate duplicate zeros between different regular systems and Huang and Wang [15] proposed a method to simplify the result. We improve Huang’s method and directly consider the symbolic representation of zeros. Once the redundancy of zeros is judged, the corresponding regular system could be deleted without changing the zeros.An early version of this paper has been reported on the 4th International Congress on Mathematical Software [23], in which the main algorithms and proofs are missing. The rest of the paper is organized as follows. In Section 2, some concepts and properties of regular systems, Gröbner basis, and resultant are introduced. Section 3 presents the main theorems. And Section 4 describes the algorithms based on the theorems in Section 3. In Section 5, we demonstrate nontrivial examples and experiment results. This paper is summarized in a brief conclusion in Section 6.


## 2. Preliminaries

Assume thatK is a field with characteristic 0 and K
[
x
1
,
…
,
x
n
] denotes the polynomial ring on K with ordered indeterminates x
1
<
x
2
<
⋯
<
x
n. For a polynomial P
∈
K
[
x
1
,
…
,
x
n
], Z
e
r
o
K
^
(
P
)
=
{
a
∈
K
^
n
∣
P
(
a
)
=
0
} is called thezero set of P, where K
^ is a field extension of K. And Z
e
r
o
K
^
(
P
) is simply denoted as Z
e
r
o
(
P
) in this paper when there is no ambiguity.Definition 1.
ForZ
⊆
K
^
n, one defines (1)
P
r
o
j
k
Z
=
x
1
,
…
,
x
k
∣
x
1
,
…
,
x
n
∈
Z
,where 1
≤
k
≤
n.LetP, Q be two polynomial sets contained in K
[
x
1
,
…
,
x
n
]. We denote Z
e
r
o
(
P
)
=
∩
P
∈
P
Z
e
r
o
(
P
), and Z
e
r
o
P
/
Q
=
Z
e
r
o
P
,
Q
=
Z
e
r
o
P
-
∪
Q
∈
Q
Z
e
r
o
(
Q
). [
P
,
Q
] is called apolynomial system.For a polynomialP
∈
K
[
x
1
,
…
,
x
n
], we say c
l
s
(
P
)
=
k, if k is the largest such that x
k appears in P. If c
l
s
(
P
)
=
k, then P has the following expression:(2)
P
=
∑
i
=
0
d
a
i
x
k
i
,where a
i
∈
K
[
x
1
,
…
,
x
k
-
1
] and a
d
≠
0. a
d is called the i
n
i
t
i
a
l of P, denoted by i
n
i
(
P
).LetP
⊆
K
[
x
1
,
…
,
x
n
]
∖
{
0
} be a polynomial set; then P
(
k
) denotes the set P
∩
K
[
x
1
,
…
,
x
k
] for 0
≤
k
≤
n. Note that P
(
n
)
=
P, P
(
0
)
=
P
∩
K.Definition 2.
A polynomial system[
P
,
Q
] is calledregular if the following conditions hold: (a)
P
(
0
)
=
∅, and c
l
s
(
P
)
≠
c
l
s
(
T
), ∀
P
∈
P, ∀
T
∈
(
P
∪
Q
)
∖
{
P
};
(b)
i
n
i
(
V
)
(
x
1
^
,
x
2
^
,
…
,
x
k
^
)
≠
0, ∀
V
∈
P
∪
Q, k
=
c
l
s
(
V
), and (
x
1
^
,
x
2
^
,
…
,
x
k
^
)
∈
Z
e
r
o
(
P
(
k
)
/
Q
(
k
)
).Proposition 3.
Let[
P
,
Q
] be a regular system; then(3)
P
r
o
j
k
Z
e
r
o
P
,
Q
=
Z
e
r
o
P
k
,
Q
k
.Regular system was proposed by [17], and an algorithm was given to decompose the zeros of a polynomial system into the union of zeros of a limited number of regular systems. Properties of regular systems could be referred to in [17, 22].Definition 4.
LetI
⊆
K
[
x
1
,
…
,
x
n
] be a nonempty polynomial ideal, and G
=
{
g
1
,
…
,
g
t
} is a finite set contained in I. G is called aGröbner basis of I, if and only if, for ∀
f
∈
I, ∃
1
≤
i
≤
t, such that l
p
(
g
i
)
∣
l
p
(
f
), where l
p
(
f
) stands for the leading power product of f under a defined term order < (e.g., lexicographical order).Proposition 5 (the elimination theorem [18, 20, 24]).
LetI
⊆
K
[
y
1
,
…
,
y
m
,
x
1
,
…
,
x
n
] be a nonempty polynomial ideal; < is a defined order such that y
i
<
x
j, where 1
≤
i
≤
m and 1
≤
j
≤
n. If G
=
{
g
1
,
g
2
,
…
,
g
t
} is a Gröbner basis of I, then G
∩
K
[
y
1
,
…
,
y
m
] is a Gröbner basis of I
∩
K
[
y
1
,
…
,
y
m
].For a polynomial idealI, we denote I
=
{
f
∣
∃
s
>
0
,
f
s
∈
I
} to be theradical of I. Note that Z
e
r
o
(
I
)
=
Z
e
r
o
(
I
). Thesaturation of I with respect to a polynomial P is defined to be the set I
:
P
∞
=
{
f
∣
∃
s
>
0
,
P
s
f
∈
I
}. Let S
⊆
K
^
n; theZariski closure
S
¯ of S is the smallest algebraic variety that contains S (see [20]).It is obvious thatI
:
P
∞
=
(
I
:
P
∞
). Furthermore,(4)
Z
e
r
o
I
:
P
∞
=
Z
e
r
o
I
∖
Z
e
r
o
P
¯
.Proposition 6.
LetI
⊆
K
[
x
1
,
…
,
x
n
] be a polynomial ideal. Given a nonzero polynomial H
∈
K
[
x
1
,
…
,
x
n
], let G be a Gröbner basis of 〈
I
,
z
H
-
1
〉 under elimination term order x
i
<
z, where z is a new added variable; then one has(5)
I
:
H
∞
=
G
∩
K
x
1
,
…
,
x
n
.LetR be a commutative ring with identity. Consider f
(
x
)
,
g
(
x
)
∈
R
[
x
]:(6)
f
x
=
a
n
x
n
+
a
n
-
1
x
n
-
1
+
⋯
+
a
0
,
a
n
≠
0
,
g
x
=
b
m
x
m
+
b
m
-
1
x
m
-
1
+
⋯
+
b
0
,
b
m
≠
0
.TheSylvester Matrix of f
(
x
) and g
(
x
) with respect to x is defined to be(7)
S
y
l
f
,
g
,
x
=
a
n
⋯
a
0
a
n
⋯
a
0
⋱
a
n
⋯
a
0
b
n
⋯
b
0
b
n
⋯
b
0
⋱
b
n
⋯
b
0
n
+
m
×
n
+
m
,where the former m rows are only related to the coefficients of f and the last n rows are only involved with the coefficients of g.We denoteR
e
s
(
f
,
g
,
x
) to be the determinant of S
y
l
(
f
,
g
,
x
). And R
e
s
(
f
,
g
,
x
) is called theresultant of f and g with respect to x. If f
(
x
1
,
…
,
x
n
)
,
g
(
x
1
,
…
,
x
n
)
∈
K
[
x
1
,
…
,
x
n
], then R
e
s
(
f
,
g
,
x
n
)
∈
K
[
x
1
,
…
,
x
n
-
1
]. Let l
c
(
f
,
x
k
) denote the leading term coefficient of f in variable x
k.Proposition 7 (see [19]).
Letf
(
x
1
,
…
,
x
n
)
,
g
(
x
1
,
…
,
x
n
)
∈
K
[
x
1
,
…
,
x
n
].(1)
If(
a
1
,
…
,
a
n
)
∈
Z
e
r
o
(
f
)
∩
Z
e
r
o
(
g
), then(8)
a
1
,
…
,
a
n
-
1
∈
Z
e
r
o
R
e
s
f
,
g
,
x
n
.
(2)
Conversely, if(
a
1
,
…
,
a
n
-
1
)
∈
Z
e
r
o
(
R
e
s
(
f
,
g
,
x
n
)
), then one of the following holds:
(a)
(
a
1
,
…
,
a
n
-
1
)
∈
Z
e
r
o
(
l
c
(
f
,
x
n
)
)
∩
Z
e
r
o
(
l
c
(
g
,
x
n
)
);
(b)
(
a
1
,
…
,
a
n
-
1
,
x
n
)
∈
Z
e
r
o
(
f
)
∪
Z
e
r
o
(
g
), where x
n is an indeterminate;
(c)
∃
a
n
∈
K
^, such that (
a
1
,
…
,
a
n
-
1
,
a
n
)
∈
Z
e
r
o
(
f
)
∩
Z
e
r
o
(
g
).Remark 8.
For a polynomialf
(
x
1
,
…
,
x
n
)
∈
K
[
x
1
,
…
,
x
n
], if f
=
∑
i
=
0
m
‍
A
i
x
k
i, where A
m
≠
0, then we denote C
o
f
(
f
,
x
k
)
=
{
A
1
,
…
,
A
m
}. Then entry (b) of statement (
2
) equals (9)
a
1
,
…
,
a
n
-
1
∈
Z
e
r
o
C
o
f
f
,
x
n
∪
Z
e
r
o
C
o
f
g
,
x
n
.Lemma 9 (see [21, 25]).
An algebraic curveC is rational if and only if g
e
n
u
s
(
C
)
=
0.


## 3. The Main Results

In this section, we consider the orthogonal projection of a rational parameterized curve onto a rational parameterized surface.Rational parameterized curves are defined as the images of mappings form(10)
Φ
:
C
⟶
R
3
,
t
⟶
Φ
t
=
Φ
1
t
Φ
0
t
,
Φ
2
t
Φ
0
t
,
Φ
3
t
Φ
0
t
,where Φ
i
(
t
)
∈
R
[
t
], i
=
0,1
,
2,3.And rational parameterized surface is defined as the images of mappings form(11)
Ψ
:
C
2
⟶
R
3
,
u
,
v
⟶
Ψ
u
,
v
=
Ψ
1
u
,
v
Ψ
0
u
,
v
,
Ψ
2
u
,
v
Ψ
0
u
,
v
,
Ψ
3
u
,
v
Ψ
0
u
,
v
,where Ψ
i
(
u
,
v
)
∈
R
[
u
,
v
], i
=
0,1
,
2,3.Given a rational parameterized curveC with parametric equation Φ
(
t
) and a rational parameterized surface S with parametric equation Ψ
(
u
,
v
), the orthogonal projection of C onto S is defined to be the set Γ
C
S of points (
u
,
v
,
t
) satisfying the following condition:(12)
Ψ
u
,
v
-
Φ
t
×
N
u
,
v
=
0
,where N
(
u
,
v
) stands for the normal vector of Ψ
(
u
,
v
) of S at (
u
,
v
). Since N
(
u
,
v
) is parallel with Ψ
u
(
u
,
v
)
×
Ψ
v
(
u
,
v
), the above condition can be written as(13)
Ψ
u
,
v
-
Φ
t
·
Ψ
u
u
,
v
=
0
,
Ψ
u
,
v
-
Φ
t
·
Ψ
v
u
,
v
=
0
.The problem of orthogonal projection is to find the solution of system (13). And note that (13) can be treated as polynomial systems, where Φ
,
Ψ are rational mappings.To study the locus of orthogonal projection in three-dimensional space, we can equivalently discuss the parametric locus of orthogonal projection. We denoteΓ
C
S
(
u
,
v
)
=
{
(
u
,
v
)
∣
∃
t
,
s.t.
(
u
,
v
,
t
)
∈
Γ
C
S
}.In the rest of the paper, letΦ
(
t
)
=
(
Φ
1
(
t
)
/
Φ
0
(
t
)
,
Φ
2
(
t
)
/
Φ
0
(
t
)
,
Φ
3
(
t
)
/
Φ
0
(
t
)
) be the parametric equation of rational curve C and let (14)
Ψ
u
,
v
=
Ψ
1
u
,
v
Ψ
0
u
,
v
,
Ψ
2
u
,
v
Ψ
0
u
,
v
,
Ψ
3
u
,
v
Ψ
0
u
,
vbe the parametric mapping of surface S.Proposition 10.
One denotes(15)
P
C
S
1
=
∑
i
=
1
3
Ψ
i
Φ
0
-
Φ
i
Ψ
0
Ψ
i
u
Ψ
0
-
Ψ
i
Ψ
0
u
,
P
C
S
2
=
∑
i
=
1
3
Ψ
i
Φ
0
-
Φ
i
Ψ
0
Ψ
i
v
Ψ
0
-
Ψ
i
Ψ
0
v
,
P
C
S
=
P
C
S
1
,
P
C
S
2
,
Q
C
S
=
Ψ
0
Φ
0
,
Q
C
S
=
Ψ
0
,
Φ
0
.Then Γ
C
S
=
Z
e
r
o
(
P
C
S
∖
Q
C
S
).Proof.
Equation (13) could be simplified as the following form by substituting Φ
(
t
) and Ψ
(
u
,
v
):(16)
∑
i
=
1
3
Ψ
i
Φ
0
-
Φ
i
Ψ
0
Ψ
i
u
Ψ
0
-
Ψ
i
Ψ
0
u
Ψ
0
3
Φ
0
,
∑
i
=
1
3
Ψ
i
Φ
0
-
Φ
i
Ψ
0
Ψ
i
v
Ψ
0
-
Ψ
i
Ψ
0
v
Ψ
0
3
Φ
0
.That implies P
C
S
1
=
0, P
C
S
2
=
0 and Ψ
0
≠
0, Φ
0
≠
0 as 0 will not be denominators.Theorem 11.
[
T
1
,
U
1
]
,
…
,
[
T
k
,
U
k
] are regular systems with the variable order u
<
v
<
t, such that Z
e
r
o
(
[
P
C
S
,
Q
C
S
]
)
=
∪
i
=
1
k
Z
e
r
o
(
[
T
i
,
U
i
]
). Then(17)
Γ
C
S
=
⋃
i
=
1
k
Z
e
r
o
T
i
,
U
i
,and Γ
C
S
(
u
,
v
)
=
∪
i
=
1
k
Z
e
r
o
(
[
T
i
(
2
)
,
U
i
(
2
)
]
).Proof.
Since it is directly thatΓ
C
S
=
Z
e
r
o
(
[
P
C
S
,
Q
C
S
]
)
=
∪
i
=
1
k
Z
e
r
o
(
[
T
i
,
U
i
]
). And the second statement of the theorem holds according to Proposition 3.Remark 12.
For the polynomial system[
P
C
S
,
Q
C
S
], an algorithm R
e
g
S
e
r
(
[
P
C
S
,
Q
C
S
],[
u
,
v
,
t
]
)
=
{
[
T
1
,
U
1
]
,
…
,
[
T
k
,
U
k
]
} such that Z
e
r
o
(
[
P
C
S
,
Q
C
S
]
)
=
∪
i
=
1
k
Z
e
r
o
(
[
T
i
,
U
i
]
) had been established [17], where [
u
,
v
,
t
] means the variable order is u
<
v
<
t.Theorem 13.
G is a Gröbner basis of(18)
I
=
P
C
S
1
,
P
C
S
2
,
z
Q
C
S
-
1under a variable order u
<
v
<
t
<
z. Then(19)
Γ
C
S
¯
=
Z
e
r
o
G
∩
R
u
,
v
,
t
.Furthermore, Γ
C
S
(
u
,
v
)
¯
=
Z
e
r
o
(
G
∩
R
[
u
,
v
]
).Proof.
According to the properties of radical ideal and saturation of ideal, we have(20)
Γ
C
S
¯
=
Z
e
r
o
P
C
S
∖
Z
e
r
o
Q
C
S
¯
=
Z
e
r
o
P
C
S
∖
Z
e
r
o
Q
C
S
¯
=
Z
e
r
o
P
C
S
:
Q
C
S
∞
=
Z
e
r
o
P
C
S
:
Q
C
S
∞
=
Z
e
r
o
P
C
S
:
Q
C
S
∞
=
Z
e
r
o
I
∩
R
u
,
v
,
t
=
Z
e
r
o
G
∩
R
u
,
v
,
t
.The last two equations hold under the statement of Proposition 6. And apparently Γ
C
S
(
u
,
v
)
¯
=
Z
e
r
o
(
G
∩
R
[
u
,
v
]
).Lemma 14.
LetP
⊆
R
[
u
,
v
,
t
] be a polynomial set and f
1
(
t
)
∈
R
[
t
], f
2
(
u
,
v
)
∈
R
[
u
,
v
]. Then P
r
o
j
2
(
Z
e
r
o
(
P
∖
{
f
1
,
f
2
}
)
)
=
P
r
o
j
2
Z
e
r
o
(
P
)
∖
Z
e
r
o
(
f
2
)
-
P
r
o
j
2
Z
e
r
o
(
P
∪
{
f
1
}
)
.Proof.
For(
u
,
v
)
∈
P
r
o
j
2
(
Z
e
r
o
(
P
∖
{
f
1
,
f
2
}
)
), that is, ∃
t, s.t. (
u
,
v
,
t
)
∈
Z
e
r
o
(
P
) and (
u
,
v
)
∉
Z
e
r
o
(
f
2
)
,
t
∉
Z
e
r
o
(
f
1
), we have (
u
,
v
)
∈
P
r
o
j
2
Z
e
r
o
(
P
)
∖
Z
e
r
o
(
f
2
)
-
P
r
o
j
2
Z
e
r
o
(
P
∪
{
f
1
}
).
Conversely, if(21)
u
,
v
∈
P
r
o
j
2
Z
e
r
o
P
∖
Z
e
r
o
f
2
-
P
r
o
j
2
Z
e
r
o
P
∪
f
1
,then ∃
t, s.t. (
u
,
v
,
t
)
∈
Z
e
r
o
(
P
)
,
(
u
,
v
)
∉
Z
e
r
o
(
f
2
)
,
t
∉
Z
e
r
o
(
f
1
). So (
u
,
v
)
∈
P
r
o
j
2
(
Z
e
r
o
(
P
∖
{
f
1
,
f
2
}
)
).
In summary,P
r
o
j
2
(
Z
e
r
o
(
P
∖
{
f
1
,
f
2
}
)
)
=
P
r
o
j
2
Z
e
r
o
(
P
)
∖
Z
e
r
o
(
f
2
)
-
P
r
o
j
2
Z
e
r
o
(
P
∪
{
f
1
}
).Theorem 15.
One has(22)
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
⊇
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
∖
Z
e
r
o
Ψ
0
⊇
Γ
C
S
u
,
v
.Furthermore, if (a)
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
∩
Z
e
r
o
l
c
P
C
S
1
,
t
∩
Z
e
r
o
l
c
P
C
S
2
,
t
=
∅,
(b)
Z
e
r
o
(
R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
)
)
∩
Z
e
r
o
(
C
o
f
(
P
C
S
1
,
t
)
)
=
∅ and Z
e
r
o
(
R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
)
)
∩
Z
e
r
o
(
C
o
f
(
P
C
S
2
,
t
)
)
=
∅,
(c)
Z
e
r
o
(
Φ
0
)
∩
Z
e
r
o
(
P
C
S
)
=
∅, then(23)
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
∖
Z
e
r
o
Ψ
0
=
Γ
C
S
u
,
v
.Proof.
Proposition7
(
1
) induces the fact that(24)
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
⊇
P
r
o
j
2
Z
e
r
o
P
C
S
,and it follows from Lemma 14 that(25)
P
r
o
j
2
Z
e
r
o
P
C
S
∖
Z
e
r
o
Ψ
0
⊇
Γ
C
S
u
,
v
.The(26)
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
⊇
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
∖
Z
e
r
o
Ψ
0
⊇
Γ
C
S
u
,
v
.Moreover, according to conditions (a), (b) and Proposition 7, we have Z
e
r
o
(
R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
)
)
=
P
r
o
j
2
Z
e
r
o
(
P
C
S
). And condition (c) induced by Lemma 14 that P
r
o
j
2
Z
e
r
o
(
P
C
S
)
∖
Z
e
r
o
(
Ψ
0
)
=
Γ
C
S
(
u
,
v
). In that way(27)
Z
e
r
o
R
e
s
P
C
S
1
,
P
C
S
2
,
t
∖
Z
e
r
o
Ψ
0
=
Γ
C
S
u
,
v
.


## 4. Algorithms

For a polynomial setP and a set M
⊆
K
^
2, we denote Z
e
r
o
(
[
P
,
M
]
)
=
Z
e
r
o
(
P
)
-
M. Then, for a polynomial system [
P
,
Q
], we have Z
e
r
o
(
[
P
,
Q
]
)
=
Z
e
r
o
(
P
)
∖
∪
Q
∈
Q
Z
e
r
o
(
Q
) = Z
e
r
o
(
P
)
∖
∪
Q
∈
Q
Z
e
r
o
(
P
∪
{
Q
}
)
=
Z
e
r
o
(
[
P
,
∪
Q
∈
Q
Z
e
r
o
(
P
∪
{
Q
}
)
]
). Letting (28)
Ω
=
T
1
,
M
1
,
…
,
T
k
,
M
k
,we define Z
e
r
o
(
Ω
)
=
∪
i
=
1
k
Z
e
r
o
(
[
T
i
,
M
i
]
).Theorem11 induces that the exact loci of projection could be decomposed into the union of zeros of regular systems, which could be in a complex form. In order to analyze the result easier, we developed an algorithm, which is improved fromSIM [15], to simplify regular systems.Proposition 16.
Algorithm1 is correct.Algorithm 1:
S
i
m
p
l
i
f
y
(
Ω
).
INPUT  Ω
=
T
1
,
U
1
,
…
,
T
k
,
U
k
OUTPUT  Θ
=
P
1
,
Q
1
,
…
,
P
m
,
Q
m,
wherem
≤
k, Q
i
⊆
C
2 and ⋃
i
=
1
k
‍
Z
e
r
o
(
[
T
i
,
U
i
]
)
=
⋃
i
=
1
m
‍
(
Z
e
r
o
(
P
i
)
-
Q
i
).
Step 1.
Ω
1
≔
∅, Ω
2
≔
∅, i
=
1, Θ
≔
∅.
For[
T
,
U
] in Ω do
IfU
≠
∅, then
ForU in U do U
≔
f
a
c
t
o
r
s
(
U
). end do;
Ω
1
≔
Ω
1
∪
T
,
U.
ElseΩ
2
≔
Ω
2
∪
T
,
U.
End do;
Step 2.
For[
T
,
U
] in Ω
1 do
Ω
1
≔
Ω
1
∖
T
,
U;
ForU in U do U
≔
Z
e
r
o
(
T
∪
U
)
If∃
T
1
,
…
,
T
k
∈
Ω
2 such that U
=
⋃
i
=
1
k
‍
Z
e
r
o
(
T
i
)
then delete[
T
i
,
∅
]
1
≤
i
≤
k from Ω
2; U
≔
U
∖
U;
Else if∃
T
1
,
…
,
T
k
∈
Ω
2 such that U
⊇
⋃
i
=
1
k
‍
Z
e
r
o
(
T
i
),
then delete[
T
i
,
∅
]
1
≤
i
≤
k from Ω
2;
U
≔
(
U
∖
{
U
}
)
∪
(
U
∖
⋃
i
=
1
k
‍
Z
e
r
o
(
T
i
)
);
Else if∃
T
1
,
…
,
T
k
∈
Ω
2 such that U
⊂
⋃
i
=
1
k
‍
Z
e
r
o
(
T
i
),
then≔
U
∖
U;
End do;
IfU
=
∅ then Ω
2
≔
Ω
2
∪
T
,
∅;
ElseΘ
≔
Θ
∪
T
,
U.
End do;
Step 3.
For[
T
,
∅
] in Ω
2 do
For[
T
′
,
U
] in Θ do
IfU
⊇
Z
e
r
o
(
T
),
thenU
≔
U
∖
Z
e
r
o
(
T
); Ω
2
≔
Ω
2
∖
T
,
∅; break;
End do;
End do;
Step 4. Return Θ
≔
Θ
∪
Ω
2.
/∗/ f
a
c
t
o
r
s
(
U
) returns all the irreducible factors of UProof.
Steps1 and 2 are similar toSIM; we only need to prove Step 3.
In Step3, if U
⊇
Z
e
r
o
(
T
), then(29)
Z
e
r
o
T
′
,
U
∪
Z
e
r
o
T
=
Z
e
r
o
T
′
∖
U
∪
Z
e
r
o
T
=
Z
e
r
o
T
′
∖
U
∖
Z
e
r
o
T
=
Z
e
r
o
T
′
,
U
∖
Z
e
r
o
T
.So T can be deleted from Ω
2 and U would be substituted by U
∖
Z
e
r
o
(
T
).Given a rational curveC and a rational surface S, Algorithm 2 computes the exact parametric loci of the orthogonal projection of C onto S.Algorithm 2:Exact parametric loci of orthogonal projection: E
P
L
O
P
(
C
,
S
).
Input  C, S
Output  Γ
C
S
(
u
,
v
).
Step 1. Generate the polynomial system [
P
C
S
,
Q
C
S
].
Step 2. Decompose [
P
C
S
,
Q
C
S
] in to the union of regular systems, Let R
e
g
S
y
s
(
[
P
C
S
,
Q
C
S
]
,
[
u
,
v
,
t
]
)
=
T
1
,
U
1
,
…
,
T
k
,
U
k.
Step 3. Let Ω
=
T
1
′
,
U
1
′
,
…
,
T
m
′
,
U
m
′
=
R
e
g
S
e
r
(
[
P
C
S
,
Q
C
S
]
,
[
u
,
v
,
t
]
)
∩
C
[
u
,
v
]
Step 4. Ω
≔
S
i
m
p
l
i
f
y
(
Ω
).
Step 5. Return Γ
C
S
(
u
,
v
)
=
Z
e
r
o
(
Ω
).Algorithm3 returns the minimal variety that contains Γ
C
S
(
u
,
v
). If d
i
m
=
0, then M
V
P
L
O
P
(
C
,
S
) consists of finitely many points. If d
i
m
=
1, then(30)
Γ
C
S
u
,
v
¯
=
Z
e
r
o
G
′
=
Z
e
r
o
G
′
=
Z
e
r
o
⋂
i
=
1
n
M
i
=
⋃
i
=
1
n
Z
e
r
o
M
i
=
⋃
i
=
1
n
Z
e
r
o
M
i
.Since 〈
M
i
〉 are prime ideals, {
Z
e
r
o
(
M
i
)
}
1
≤
i
≤
n are irreducible components of Γ
C
S
(
u
,
v
)
¯ that do not contain each other. If d
i
m
=
2, then Γ
C
S
(
u
,
v
)
¯ equals the whole parametric plane.Algorithm 3:Minimal variety that contains the parametric loci of orthogonal projection: M
V
P
L
O
P
(
C
,
S
).
Input  C, S
Output  Γ
C
S
(
u
,
v
)
¯.
Step 1. Generate the polynomial system [
P
C
S
,
Q
C
S
].
Step 2. Compute the Gröebner basis G of 〈
P
C
S
1
,
P
C
S
2
,
z
Q
C
S
-
1
〉 under the term order such that u
<
v
<
t
<
z.
Step 3. Let G
′
=
G
∩
C
[
u
,
v
]. Let d
i
m to be the dimension of Z
e
r
o
(
G
′
).
Step 4. If d
i
m
=
0, then return Z
e
r
o
(
G
′
).
Step 5. If d
i
m
=
1, then decompose 〈
G
′
〉 into the intersection of prime ideals: 〈
G
′
〉
=
⋂
i
=
1
n
‍
〈
M
i
〉.
Return⋃
i
=
1
n
‍
Z
e
r
o
(
M
i
).
Step 6. If d
i
m
=
2, return Z
e
r
o
(
0
).Algorithm4 calculates a variety that contains Γ
C
S
(
u
,
v
). Note that R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
) is a polynomial in R
[
u
,
v
] and ∏
i
=
1
n
‍
f
i factorize R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
) into irreducible algebraic curves. For each irreducible algebra curve f
i, if G
e
n
u
s
(
f
i
)
=
0, then f
i can be rational parameterized.Algorithm 4:Parametric loci of orthogonal projection: A
P
L
O
P
(
C
,
S
).
Input  C, S, where m
a
x
0
≤
i
≤
3
d
e
g
r
e
e
(
Φ
i
(
t
)
)
>
0.
Output A variety that contains Γ
C
S
(
u
,
v
).
Step 1. Generate the polynomial system [
P
C
S
,
Q
C
S
].
Step 2. Compute R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
).
Step 3. Factorize R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
)
=
∏
i
=
1
n
f
i, f
i is a irreducible factor of R
e
s
(
P
C
S
1
,
P
C
S
2
,
t
) in R
[
u
,
v
].
Step 4.
LetV
≔
∅;
Fori
=
1 to n do
g
≔
G
e
n
u
s
(
f
i
);
Ifg
>
0, V
≔
V
∪
Z
e
r
o
(
f
i
).
ElseV
≔
V
∪
P
a
r
a
m
e
t
r
i
z
a
t
i
o
n
(
f
i
,
t
).
End for
Step 5. Return V.
/∗/P
a
r
a
m
e
t
r
i
z
a
t
i
o
n
(
f
i
,
t
) [21] returns the parametric presetations of f
i in parameters t.Theorem 17.
One has(31)
E
P
L
O
P
C
,
S
⊆
M
V
P
L
O
P
C
,
S
⊆
A
P
L
O
P
C
,
S
.Proof.
It is a direct consequence of the above discussion that(32)
E
P
L
O
P
C
,
S
⊆
M
V
P
L
O
P
C
,
S
,
E
P
L
O
P
C
,
S
⊆
A
P
L
O
P
C
,
S
.Note that M
V
P
L
O
P
(
C
,
S
) and A
P
L
O
P
(
C
,
S
) are varieties. And M
V
P
L
O
P
(
C
,
S
) is the minimal variety that contains Γ
C
S
(
u
,
v
); then M
V
P
L
O
P
(
C
,
S
)
⊆
A
P
L
O
P
(
C
,
S
).


## 5. Examples and Comparison

Example 1 (point projection).
Consider the algebraic surfaceS:(33)
Ψ
u
,
v
=
Ψ
1
u
,
v
Ψ
0
u
,
v
,
Ψ
2
u
,
v
Ψ
0
u
,
v
,
Ψ
3
u
,
v
Ψ
0
u
,
v
,where Ψ
1
(
u
,
v
)
=
2
v
-
u
2, Ψ
2
(
u
,
v
)
=
-
u
2
+
3
u
v, Ψ
3
(
u
,
v
)
=
7
v
-
u, Ψ
0
(
u
,
v
)
=
1. Let P
=
(
-
10,0
,
30
) be a point in 3D space. P could be treated as a constant function with variable t.
Algorithm2 yields {
[
{
P
1
,
P
2
}
,
∅
]
}, where(34)
P
1
=
-
53
v
+
2
u
2
+
190
+
3
u
3
-
9
u
2
v
+
7
u
,
P
2
=
6890
+
114326
u
-
26133
u
2
-
5883
u
3
-
2208
u
4
+
216
u
5
-
81
u
6
+
81
u
7
.Algorithm 3 returns the same loci as above. Since {
P
1
,
P
2
} is a triangular system, it is easy to check that Z
e
r
o
(
P
1
,
P
2
) contains only finitely isolated points. The point projections are shown in Figure 1.Figure 1
Projection ofP onto S in Example 1.Example 2.
We consider a simple case with an algebraic surfaceS: Ψ
(
u
,
v
)
=
(
v
2
+
u
,
4
u
v
+
2
,
u
2
+
3
) and an algebraic curve C: Φ
(
t
)
=
(
t
+
3
,
-
2
t
,
5
t
+
5
).
Firstly,(35)
P
C
S
1
u
,
v
,
t
=
8
v
-
10
u
-
1
t
+
v
2
+
u
+
2
u
2
-
2
u
-
3
+
4
4
u
v
+
2
v
,
P
C
S
2
u
,
v
,
t
=
8
u
-
2
v
t
+
2
v
2
+
u
-
3
v
+
4
4
u
v
+
2
u
.
In Step3 of Algorithm 2, Ω
=
T
1
,
U
1
,
T
2
,
U
2
,
T
3
,
U
3, where(36)
T
1
=
-
13
u
v
+
9
u
2
v
-
4
u
-
4
v
4
-
2
u
v
2
+
8
v
2
-
3
u
v
2
+
39
u
3
v
+
14
u
2
+
4
u
4
,
U
1
=
-
3278
u
+
10228
u
2
+
38016
u
4
+
7512
u
3
+
127
,
T
2
=
1
-
8
v
+
10
u
,
-
492
v
2
-
1351
+
2824
v
+
6912
v
3
,
T
3
=
-
3278
u
+
10228
u
2
+
38016
u
4
+
7512
u
3
+
127,3392
u
3
+
412
u
2
-
1280
u
2
v
-
464
u
v
-
452
u
-
1024
u
v
2
+
1016
v
+
127
-
64
v
2
-
512
v
3
,
U
2
=
∅
,
U
3
=
∅
.
And Huang’s [15] algorithm S
I
M outputs {
[
T
1
,
U
]
,
[
T
3
,
∅
]
}, where(37)
U
=
1
22
,
2
11
,
1
22
R
o
o
t
O
f
4
Z
3
+
19
Z
2
-
3752
Z
-
8953
,
1
22
,
1
2
α
,
β
,
α
=
R
o
o
t
O
f
216
Z
3
+
105
Z
2
+
242
Z
-
127
,
β
=
R
o
o
t
O
f
-
1728
Z
3
+
1728
+
216
Z
2
+
1080
-
3429
Z
-
1270
+
348
α
2
+
2366
α
.
While algorithmS
i
m
p
l
i
f
y
(
Ω
) yields {
[
T
1
,
{
(
1
/
22
,
2
/
11
)
}
]
}, compared with algorithm S
I
M, algorithm S
i
m
p
l
i
f
y returns a more laconic result by directly computing the zero sets.
Algorithm3 returns Z
e
r
o
(
-
13
u
v
+
9
u
2
v
-
4
u
-
4
v
4
-
2
u
v
2
+
8
v
2
-
3
u
v
2
+
39
u
3
v
+
14
u
2
+
4
u
4
), while Algorithm 4 returns the same variety, as shown in Figure 2. And G
e
n
u
s
(
-
13
u
v
+
9
u
2
v
-
4
u
-
4
v
4
-
2
u
v
2
+
8
v
2
-
3
u
v
2
+
39
u
3
v
+
14
u
2
+
4
u
4
)
=
3, so the variety could not be rational parameterized. Furthermore, p
(
1
/
22
,
2
/
11
)
∈
Z
e
r
o
(
l
c
(
P
C
S
1
,
t
)
)
∩
Z
e
r
o
(
l
c
(
P
C
S
2
,
t
)
), so (
1
/
22
,
2
/
11
) is not in the exact parametric of the loci.Figure 2
Parametric loci and 3D curve of orthogonal projection for Example2.Example 3.
Consider the algebraic surfaceS: Ψ
(
u
,
v
)
=
(
Ψ
1
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
,
Ψ
2
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
,
Ψ
3
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
), where(38)
Ψ
0
u
,
v
=
1
,
Ψ
1
u
,
v
=
-
94.4
+
88.9
v
+
5.6
v
2
,
Ψ
2
u
,
v
=
-
131.3
u
+
28.1
u
2
,
Ψ
3
u
,
v
=
5.9
u
2
v
2
+
u
2
v
-
3.9
v
2
u
+
76.2
u
2
+
6.7
v
2
-
27.3
u
v
-
50.8
u
+
25
v
+
12.1
.We randomly pick a curve C: Φ
(
t
)
=
(
Φ
1
(
t
)
/
Φ
0
(
t
)
,
Φ
2
(
t
)
/
Φ
0
(
t
)
,
Φ
3
(
t
)
/
Φ
0
(
t
)
) passing over S, where(39)
Φ
1
t
=
-
90
t
-
1
t
+
5
,
Φ
2
t
=
-
4
t
-
200
,
Φ
3
t
=
-
5
t
+
30
t
+
5
,
Φ
0
t
=
t
+
5
.
S is a common surface in mold industry [26] and is also a popular test surface for CNC machining methods. And note that C is a rational curve.
Algorithm2 yields {
[
T
1
,
U
1
]
,
[
T
2
,
∅
]
,
[
T
3
,
∅
]
,
[
T
4
,
∅
]
}, where(40)
T
1
=
M
,
U
1
=
α
1
,
β
1
,
α
2
,
β
2
,
M
=
129735449752
u
9
v
4
+
⋯
82
t
e
r
m
s
,
T
2
=
T
3
=
T
4
=
2
.Since T
2
,
T
3
,
T
4 are triangular systems with two elements, ∪
i
=
2
4
Z
e
r
o
(
T
i
) consisted of finite points. Furthermore, one could check that ∪
i
=
2
4
Z
e
r
o
(
T
i
)
⊆
Z
e
r
o
(
[
T
1
,
U
1
]
). So the exact parametric locus of orthogonal projection is Z
e
r
o
(
[
T
1
,
U
1
]
). And moreover (
α
1
,
β
1
,
-
5
) and (
α
2
,
β
2
,
-
5
) are in Z
e
r
o
(
P
C
S
), while t
=
-
5 is not in the domain of Φ
(
t
).
Algorithm3 returns Z
(
M
). And one can obtain Z
(
M
)
∪
Z
(
u
-
1313
/
562
) by means of Algorithm 4. Compared with Algorithm 3, u
-
1313
/
562 is a redundant branch of the projective loci. As a matter of fact, (
1313
/
562
,
v
,
-
5
) is a zero of P
C
S, while t
=
-
5 is not in the domain of Φ
(
t
). The results are illustrated in Figure 3.Figure 3
Parametric loci and 3D curve of orthogonal projection for Example3.Example 4.
LetS: Ψ
(
u
,
v
)
=
(
Ψ
1
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
,
Ψ
2
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
,
Ψ
3
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
), where(41)
Ψ
1
u
,
v
=
u
+
2
v
2
,
Ψ
2
u
,
v
=
3
u
2
+
1
,
Ψ
3
u
,
v
=
v
+
2
,
Ψ
0
u
,
v
=
u
+
v
+
2
,and let C: Φ
(
t
)
=
(
Φ
1
(
t
)
/
Φ
0
(
t
)
,
Φ
2
(
t
)
/
Φ
0
(
t
)
,
Φ
3
(
t
)
/
Φ
0
(
t
)
), where(42)
Φ
1
t
=
-
90
t
-
1
,
Φ
2
t
=
-
4
t
-
200
,
Φ
3
t
=
t
+
2
,
Φ
0
t
=
t
+
5
.Note that S and C are both rational.
Algorithm2 returns(43)
Z
e
r
o
M
,
α
1
,
β
1
,
α
2
,
β
2
,
α
3
,
β
3
,where(44)
M
=
-
33019
v
+
4592
u
-
27012
u
2
-
1017
u
4
-
13776
u
3
-
507
v
3
-
3
v
4
+
58308
u
v
3
+
1080
u
2
v
3
+
1080
v
4
u
+
4041
u
3
v
2
+
108246
v
2
u
2
+
419468
u
v
-
18716
v
2
+
70692
u
3
v
+
312582
u
2
v
+
325363
u
v
2
+
4041
v
u
4
+
9117
;
α
1
=
-
2
-
β
1
,
α
2
=
113
270
-
449
270
β
2
,
β
1
=
R
o
o
t
O
f
102379
Z
+
14179
+
125682
Z
2
+
11532
Z
4
+
62620
Z
3
;
β
2
=
R
o
o
t
O
f
80371
Z
2
-
586394
Z
-
11531
;
α
3
=
0.0000008327858555
β
3
11
+
⋯
-
0.4481487421
,
β
3
=
R
o
o
t
O
f
7488
Z
12
+
⋯
+
555282888
.One can check that (
α
1
,
β
1
) is root of u
+
v
+
2, which could not be vanished as denominator. (α
2
,
β
2
,
-
5) is a root of P
C
S, vanishing t
+
5. And(45)
P
C
S
1
α
3
,
β
3
,
t
=
c
1
≠
0
,
P
C
S
2
α
3
,
β
3
,
t
=
c
2
≠
0
,where c
1
,
c
2 are constants that do not involve t.
Algorithm3 yields Z
e
r
o
(
M
), which represents the minimal variety that contains the projection loci.
And the output of Algorithm4 is Z
e
r
o
(
M
)
∪
Z
e
r
o
(
u
+
v
+
2
). The redundant branch Z
e
r
o
(
u
+
v
+
2
) is outside the domain of Ψ
(
u
,
v
). Figure 4 shows the projections of the example.Figure 4
Parametric loci and 3D curve of orthogonal projection for Example4.More examples have been computed with a 3 GHz CPU and 2 GB memories. And the cost of time for each algorithm has been demonstrated in Table1. And Table 2 records the number of solutions before simplified, solutions simplified viaSIM and solutions simplified usingSimplify. “Y” in the chart induces the fact that Algorithm 4 has redundant branches with respect to the result of Algorithm 3, and “N” for no redundant branches. “NA” means the result is not available in 3600 s or the memory reached the hardware limit. In each example, let rational curve be C: Φ
(
t
)
=
(
Φ
1
(
t
)
/
Φ
0
(
t
)
,
Φ
2
(
t
)
/
Φ
0
(
t
)
,
Φ
3
(
t
)
/
Φ
0
(
t
)
) and let rational surface be S: Ψ
(
u
,
v
)
=
(
Ψ
1
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
,
Ψ
2
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
,
Ψ
3
(
u
,
v
)
/
Ψ
0
(
u
,
v
)
); then D
e
g
r
e
e
(
a
,
b
,
c
,
d
) mean m
a
x
1
≤
i
≤
3
d
e
g
r
e
e
(
Ψ
i
)
=
a, d
e
g
r
e
e
(
Ψ
0
)
=
b, m
a
x
1
≤
i
≤
3
d
e
g
r
e
e
(
Φ
i
)
=
c, and d
e
g
r
e
e
(
Φ
0
)
=
d.Table 1
Time cost of the algorithms.
Degree
Algorithm2
Algorithm3
Algorithm4
Redundancy
EX1
(1, 0, 1, 0)
0.016 s
0.016 s
<0.001 s
N
EX2
(2, 0, 1, 0)
0.188 s
0.063 s
<0.001 s
N
EX3
(3, 0, 1, 0)
0.032 s
0.468 s
0.016 s
N
EX4
(4, 0, 1, 0)
0.734 s
2.671 s
<0.001 s
N
EX5
(2, 0, 2, 0)
0.203 s
0.031 s
<0.001 s
N
EX6
(3, 0, 2, 0)
596.797 s
0.047 s
<0.001 s
N
EX7
(1, 1, 1, 1)
0.078 s
0.016 s
<0.001 s
Y
EX8
(2, 1, 2, 1)
0.891 s
0.297 s
0.016 s
Y
EX9
(2, 2, 2, 1)
0.078 s
0.015 s
0.032 s
Y
EX10
(2, 2, 2, 2)
1.515 s
0.984 s
0.016 s
Y
EX11
(3, 1, 2, 1)
NA
113.938 s
0.016 s
YTable 2
Comparison on simplification methods (number of elements).
RegSer
SIM
Simplify
EX1
1
1
1
EX2
3
3
3
EX3
4
2
2
EX4
6
3
2
EX5
4
1
1
EX6
8
2
2
EX7
2
1
1
EX8
7
2
1
EX9
2
1
1
EX10
6
2
1
EX11
NA
NA
NATable1 illustrates that Algorithm 2 performs well in low degree case, but the time cost increases fast while the degree of surface and curve increasing; this is because the degree and the number of output regular systems in Step 3 are getting enormous (see EX6 and EX11). Since most commonly used surfaces and curves have low degree, Algorithm 2 is valuable for engineering practice.Algorithm3 is significantly better than Algorithm 2 at time cost and works fine while the input degree grows.Algorithm4 performs in a steady and excellent way at the computation cost, but it always generates redundant branches when the inputs are rational.Table2 induces the fact that the algorithm S
i
m
p
l
i
f
y could reduce the number of regular systems for the parametric loci in most circumstances. And, compared with S
I
M, our algorithm has a more concise output.


## 6. Conclusions

In this paper, three algorithms for computing orthogonal projection of a rational curve onto rational parametric surface were presented. The methodE
P
L
O
P based on regular systems could compute the exact parameter loci of the projection, Algorithm M
V
P
L
O
P computes the minimal variety that contains the parameter loci of the projection, and A
P
L
O
P returns a variety passing through the parameter loci of the projection. We also developed the algorithm S
i
m
p
l
i
f
y to simplify a series of regular systems. Preliminary examples showed that our algorithms work well and are valuable.



---

*Source: 394246-2015-07-16.xml*