Database Reference
In-Depth Information
c be a line of slope 1. If we move this line slightly to
the left or to the right, it still intersects the same number of line segments,
unless we cross an endpoint of a line segment. In this case, the set of inter-
sected line segments increases or decreases by one. There are
Proof: Let
f c (
x
)=
x
+
))
endpoints. A line of slope 1 that sweeps all the endpoints will therefore
intersect at most
O
(
δ
(
n
+
m
O
(
δ
(
n
+
m
)) different sets of line segments during the
sweep.
)) translations that produce
different sets of potential matchings by finding the lines of slope 1 that
pass through the endpoints. Each such translation corresponds to a line
f c (
In addition, we can enumerate the
O
(
δ
(
n
+
m
)) translations gives all possible
matchings for a longest common subsequence of
x
)=
x
+
c .Thissetof
O
(
δ
(
n
+
m
A, B
. Since running the
LCSS algorithm takes
O
(
δ
(
n
+
m
)) we have shown the following theorem:
Theorem 1. Given two sequences A and B, with
|A|
=
n
and
|B|
=
m
,
) 2 δ 2 ) time.
we can compute the
S
2(
δ, ε, A, B
) in
O
((
n
+
m
4.3. An Ecient Approximate Algorithm
Theorem 1 gives an exact algorithm for computing
2, but this algorithm
runs in quadratic time. In this section we present a much more ecient
approximate algorithm. The key in our technique is that we can bound the
difference between the sets of line segments that different lines of slope 1
intersect, based on how far apart the lines are.
Let us consider the
S
)) translations that result to different
sets of intersected line segments. Each translation is a line of the form
f c (
O
(
δ
(
n
+
m
x
x
c . Let us sort these translations by
c . For a given translation
)=
+
f c ,let
L fc be the set of line segments it intersects. The following lemma
shows that neighbor translations in this order intersect similar sets of line
segments.
c 1 ,...,f N (
c N
Lemma 3. Let
f 1 (
x
)=
x
+
x
)=
x
+
be the different transla-
c 1 ≤ ··· ≤ c N
tions for sequences
A x and
B x , where
. Then the symmetric
difference
L fi
L fj ≤|i − j|
.
Proof: Without loss of generality, assume
i<j
. The difference between
f i
and
f i +1 is simply that we cross one additional endpoint. This means that
we have to either add or subtract one line segment to
L fi to get
L fi +1 .By
repeating this step (
j − i
) times we create
L fj .
Search WWH ::




Custom Search