Biomedical Engineering Reference
In-Depth Information
Eq. (
1.7
) replaces the radius growth which consists of adding
α
to the squared radius,
as in Eq. (
1.4
).
Curved Voronoı diagrams.
The growth process just defined is coupled to curved
Voronoı diagrams and
α
-shapes. To see why, let
p
be a point belonging to the grown
ball of Eq. (
1.7
). Denoting
δ
i
=
r
i
− r
i
, observe that
r
i
(
λ
)=
|| c
i
p ||⇔ λ
=
1
δ
i
(
|| c
i
p || −r
i
)
.
(1.8)
That is, given a point
p
, we can define the function
λ
(
B
i
,p
) corresponding to the
value of
λ
such that
p
is on the corresponding grown ball. Denoting
μ
i
=1
/δ
i
and
α
i
=
r
i
/δ
i
, this latter equation can be rewritten as:
λ
(
B
i
,p
)=
μ
i
|| c
i
p || −α
i
.
(1.9)
In this equation, the Euclidean distance is multiplicatively weighted by
μ
i
,and
additively weighted by
α
i
. The associated Voronoı diagram is termed
compoundly-
weighted
[
51
], CW for short, and consists of the partition of the 3D space into the
Voronoı regions defined by:
Vo r(
B
i
)=
{p ∈ E
3
such that
λ
(
B
i
,p
)
≤ λ
(
B
j
,p
)
, ∀B
j
=
B
i
}.
(1.10)
Intuitively, a po
int
p
belo
ng
s to Vor(
B
i
) if the
gr
owing ball
B
i
[
λ
] reaches point
p
before any ball
B
j
[
λ
] =
B
i
[
λ
]. A region Vor(
B
i
) is bounded by curved bisectors,
which are degree four algebraic surfaces. See Fig.
1.10
for a 2D example. Note
that a Voronoı cell may not be (simply) connected. While a naıve algorithm has
recently been developed to compute such diagrams [
12
], as opposed to affine
Voronoı diagrams, both the complexity of CW diagrams and the design of efficient
algorithms are open problems.
λ
-complex.
To compute complexes and mixtures in the bicolor
setting, w
e g
eneralize the
α
-shapes of Sect.
1.2.2
to the CW Voronoı diagram. For a
giv
en ball
B
i
[
λ
], consider its
restriction
to its Voronoı region, that is the intersection
B
i
[
λ
]
∩
-shapes and the
λ
Vo r (
B
i
). These restrictions naturally partition the domain
F
λ
,andtheir
connected components correspond to the aforementioned complexes.
In using the
λ
-complex, one needs to decide up to which value
λ
max
the growth
process is performed. This value is defined using the following volumetric criterion.
Consider a complex
C
, namely a connected component of
F
λ
, and denote its
volume
Vol
λ
(
C
), that is the sum of the volumes of its restrictions in the CW
Voronoı diagram. (As computing these volumes, which are bounded by degree four
algebraic surfaces, is an open problem, a practical alternative consists of adding up
the volumes of the restrictions in the power diagram of the grown balls, as explained
in Sect.
1.2.3
.) Since this complex corresponds to a list of toleranced proteins, let
Vol
ref
be the sum of the reference volumes of these proteins [
33
]. (The reference
volume of a protein is estimated from its sequence of amino-acids. These reference
Search WWH ::
Custom Search