**Expected
Performance**

As I mentioned earlier, the correctness of the algorithm follows directly from the loop invariant, so the only thing we what needs to be do is the performance analysis.

For some insertion orders, the
resulting search structure may have quadratic size and linear search time. For
other permutations it is much better. We took a random insertion sequence, so
we are interested in the *expected *performance. The expected time is the
average of the running time, taken over all *n*! permutations

**Theorem.**

- This algorithm computes

andTfrom a setDn line segments in general position in O(Snlogn) expected time

- The expected size ofis O(Dn)

- For any query pointqthe expected query time is O(logn)

**Proof:
Expected Query Time is O(log n)**

Fix a query point *q*, and
consider the path in ** D** traversed by the query.

Define

*S** _{i}* = {

X

P

From
our construction, X* _{i}* £ 3; thus

*P _{i}* = Pr[D

Backwards
analysis:

How
many segments in *S** _{i}* affect D

Let H

_{n}= 1 + 1/2 + 1/3 + ... + 1/n, and recall that H_{n}= Θ(log n), in particular for n > 1 we have log_{e }n < H_{n}< 1 + log_{e}n.

**Proof:
Expected Storage Size is O( n)**

The
total number of nodes is bounded by

where

k= number of new trapezoids created in iteration_{i}i.

Define d(D,s) = |
{ |
1 if D disappears
from S) when _{i}s is
removed from S_{i} |

0 otherwise |

So, the expected amount of storage is O(n).

**Proof:
Expected Construction Time is O( n log n)**

The
time to insert segment *s _{i}* is O(

So, the expected running time of the algorithm is

Using tail estimate one can prove that let ** S** be set non-crossing
line segments and let l be a parameter with
l > 0. Then the probability that the maximum length
of a search path in the structure for

**Surprise** **surprise** this is not end of the story, Raimund Seidel [8]
has showed that if ** S** is given as a simple polygonal chain the
expected running time of his algorithm is O(

**Removing Our
Assumptions**

We can get rid of the assumption
that no two distinct endpoints have the same x-coordinate.

Observation: The vertical direction that we chose was
immaterial.

1st Idea: Rotate the axis system
slightly

This
can lead to numerical difficulties, and requires an extra pass through the
data.

Improved
Idea: Apply affine mapping (shear transformation)

F(x, y)=(x + ey, y) for small enough e.

This
mapping preserves straight lines, so any "insidedness" holds just as
true as it did before we applied the shear.

**Symbolic
Transformation**

In practice, we don’t have to
apply any transformation. We get the result using lexicographic order (compare
first by x-coordinate, then by y-coordinate):

The only two operations used in the
algorithm were:

Decide
if *q* lies to the left of *p*, to the right, or on the vertical line
through *p*.

Decide whether *q* lies above, below, or on the segment with endpoints *p*_{1}
and *p*_{2}.

Both
can be done without actually computing F.
Moreover, it is equivalent to the
limit of these shears as e approaches zero (from the positive
side).

This
modification also makes the other initial assumption unnecessary: A query point
never lies on the vertical line of a point node, or on the segment of a segment
node.

**Conclusion: **
Our algorithm** TrapezoidalMap **computes the
trapezoidal map * T*(