The Lower Envelope: The Pointwise Minimum of a Set of Functions

Computational Geometry, WS 2007/08Lecture 4

Prof. Dr. Thomas Ottmann

Algorithmen & Datenstrukturen, Institut für InformatikFakultät für Angewandte WissenschaftenAlbert-Ludwigs-Universität Freiburg

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 2

Overview

• Definition of the Lower Envelope.• Functions: Non-linear, x-monotone.• Techniques: Divide & conquer, Sweep-line.

• Definition: s(n).

• Davenport-Schinzel Sequences (DSS).• Lower Envelope of n line segments.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 3

The Lower Envelope

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 4

Definition of the Lower Envelope

Given n real-valued functions, all defined on a common interval I,

then the minimum is :

f(x) = min 1≤i≤n fi (x)

The graph of f(x) is called the lower envelope of the fi’s.

y =-∞

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 5

Special Case

If all the functions fi are linear, then their graphs are line segments.

The lower envelope can be calculated with the help of sweep algorithm.

A

B

C

D

Cu

I

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 6

Non-Linear Functions

Question: Could the sweep line method also be used to find the lower envelope of graphs of non-linear functions?

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 7

X-Monotone Functions

• A curve c is x-monotone if any vertical line either does not intersect c, or it intersects c at a single point.

• Assumptions– All functions are x-monotone.– Function evaluation and determination of intersection points take

time O(1). – The space complexity of the description of a function fi is also

constant.

Theorem 1: With the sweep technique, the k intersection points of n different x-monotone curves can be computed in O((n+k) log n) time and O(n) space.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 8

The Sweep Technique

• If any two curves intersect in at most s points, (this would be satisfied when the functions of all n curves are polynomials that have degree at most s), then the total number of intersection points k is

k ≤ s*n(n-1)/2

Consequence:• The total time complexity of the sweep line algorithm for computing

the lower envelope of n x-monotone functions is O(s n2 log n) (from the O((n+k) log n) bound for computing all k intersection points).

Note:• This is NOT an output-sensitive algorithm.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 9

Example

S=3,n=4

Maximum k=18

Only 8 intersection points needed for lower envelope!

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 10

New: Divide & Conquer, Sweep-line

If n =1, do nothing, otherwise:

1. Divide: the set S of n functions into two disjoint sets S1 and S2 of size n/2.

2. Conquer: Compute the lower envelopes L1 and L2 for the two sets S1 and S2 of smaller size.

3. Merge: Use a sweep-line algorithm for merging the lower envelopes L1 and L2 of S1 and S2 into the lower envelope L of the set S.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 11

Example: Divide & Conquer

Lower envelope of curves A and D

Lower envelope of curves C and B

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 12

Sweep-line: Merging 2 Lower Envelopes

Sweep over L1 and L2 from left to right:

Event points: All vertices of L1 and L2,

all intersection points of L1 and L2

At each instance of time, the event queue contains only 3 points:

– 1 (the next) right endpoint of a segment of L1

– 1 (the next) right endpoint of a segment of L2

– The next intersection point of L1 and L2, if it exists.

Sweep status structure: Contains two segments in y-order

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 13

Handling the Events

@Initialization:

• Retrieve segments (a0,a1) and (b0,b1)

• Test for intersection(s) • Initialize the event Q with

@Segment endpoint:• Retrieve next right endpoint • Test for intersection(s) • Insert into the event Q

@Intersection point:• Simply

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 14

Example: Sweep-line

Event Q:

SSS:

Output L:

L1

L2

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 15

Time Complexity

The lower envelope can be computed in time proportional to the number of events (halting points of the sweep line).

At each event point, a constant amount of work is sufficient to update the SSS and to output the result.

Total runtime of the merge step: O(#events).

How large is this number?

L1

L2

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 16

Definition: s(n)

The maximum number of segments of the lower envelope of an arrangement of

• n different x-monotone curves over a common interval• such that every two curves have at most s intersection points

λs(n) is finite and grows monotonously with n.

λs(n/2) ≤ λs(n)

Lower envelopeof a set of n/2x-monotone curves

Lower envelopeof a set of n/2x-monotone curves

L1

L2

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 17

Analysis

If n =1, do nothing, otherwise:

1. Divide: the set S of n functions into two disjoint sets S1 and S2 of size n/2.

2. Conquer: Compute the lower envelopes L1 and L2 for the two sets S1 and S2 of smaller size.

3. Merge: Use a sweep-line algorithm for merging the lower envelopes L1 and L2 of S1 and S2 into the lower envelope L of the set S.

Time complexity T(n) of the D&C/Sweep algorithm for a set of n x-monotone curves, s.t. each pair ofcurves intersects in at most s points:

T(1) = CT(n) ≤

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 18

Analysis

Using the Lemma : For all s, n ≥ 1, 2λs(n) ≤ λs(2n),

and the recurrence relation T(1) = C, T(n) ≤ 2 T(n/2) + C λs(n) yields:

Theorem: To calculate the lower envelope of n different x-monotone curves on the same interval, with the property that any two curves intersect in at most s points can be computed in time O(λs(n) log n ).

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 19

Recursion Tree

Back-substitution

The root has cost of Cλs(n)

each subtree has cost of Cλs(n/2)

By induction….

each subtree has cost of Cλs(n/4)

Marking each node with the cost of the divide and conquer step

T(n)

T(n/2) T(n/2)

T(n/4) T(n/4) T(n/4) T(n/4)

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 20

Davenport-Schinzel Sequences (DSS)

Consider words (strings) over an alphabet {A, B, C,…} of n letters.

A DSS of order s is a word such that• no letter occurs more than once on any two consecutive positions• the order in which any two letters occur in the word changes at

most s times.

Examples: ABBA is no DSS, ABDCAEBAC is DSS of order 4,

What about ABRAKADABRA?

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 21

Davenport-Schinzel Sequences (DSS)

Theorem:The maximal length of a DSS of order s over an alphabet of n letters is λs(n).

Proof part 1: Show that for each lower envelope of n x-monotone curves, s.t. any two of them intersect in at most s points, there is a DSS over an n-letter alphabet which has the same length (# segments) as the lowerenvelope.

Proof part 2: Show that for each DSS of length n and order sthere is a set of n x-monotone curves which has the property that any two curves intersect in at most s points and which have alower envelope of n segments.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 22

DSS: Proof (Part 1)

A AC

DC B

B

DC

Lower envelope contains the segments ABACDCBCD in this order.

It obviously has the same length as the l.e. Is this also a DSS?

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 23

Example: DSS

A

B

C

A

A

A

B

B

C

C

C

Example: Davenport-Schinzel-Sequence: ABACACBC

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 24

DSS: Proof (Part 2)

Proof part 2: Given a DSS w of order s over an alphabet of n letters, construct an arrangement of n curves with the property that each pair of curves intersects in at most s point which has w as its lower envelope.

Generic example: ABCABACBA, DSS of order 5

A

B

C

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 25

Lemma

Lemma: For all s,n ≥ 1: 2 λs(n) ≤ λs(2n)

Proof: Given a DSS over an n-element alphabet of order s and length l;construct a DSS of length 2l over an alphabet of 2n letters by concatenating two copies of the given DSS and choosing new letters for the second copy.

Example:n = 2, that is, choose alphabet {A,B}, s = 3, DSS3 = ABAB

n= 4, that is, choose alphabet {A,B,C,D}

ABABCDCD is a DSS of order 3 and double length.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 26

Properties of s(n)

1. λ1(n) = n

2. λ2(n) = 2n -1

3. λs(n) ≤ s (n – 1) n / 2 + 1

4. λs(n) O(n log* n), where log*n is the smallest integer m, s.t. the m-th iteration of the logarithm of n

log2(log2(...(log2(n))...))yields a value ≤ 1:

Note: For realistic values of n, the value log*n can be considered as constant!

Example: For all n ≤1020000 , log*n ≤5

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 27

Lower Envelope of n Line-Segments

A

B

C

D

Cu

Theorem: The lower envelope of n line segments over a common interval can be computed in time O(n log n) and linear space.

Proof: λ1(n) = n

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 28

Line-Segments in General Position

A

BC D

A

AB

B

D

Theorem: The lower envelope of n linesegments in general position has

O(λ3(n))many segments. It can be computed in time O(λ3(n) log n).

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 29

Reduction to X-Monotone Curves

A

BC

D

A

AB

B

D

Any two curves mayIntersect at most3 times!

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 30

Reduction to X-Monotone Curves

Any two curves mayIntersect at most3 times!

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 31

Analysis

Because the outer segments are parallel to each other, any two x-monotone curves can intersect in at most three points.

Therefore, the lower envelope has at most O(λ3(n) log n) segments.

It is known that λ3(n) Θ(n α(n)). Here, α is the functional inverse of the Ackermann function A defined by:

A(1, n) = 2n , if n ≥ 1A(k, 1) = A(k – 1, 1) , if k ≥ 2A(k, n) = A(k – 1, A(k, n – 1)) , if k ≥ 2, n ≥ 2

Define a(n) = A(n, n), then α is defined by α(m) = min{ n; a(n) ≥ m}

The function α(m) grows almost linear in m (but is not linear).

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 32

References

1. R. Klein. Algorithmische Geometrie, Kap. 2.3.3. Addison Wesley, 1996.

2. M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and their Geometric Applications, Cambridge University Press, 1995.