Design & Analysis ofInformation Systems
Mathematics in Computer Science.
This year’s topic is
Computational Geometry.

Mathematics in computer science• Mathematics seeks for elegant solutions– “Solution” is not just “showing the answer”.
– It is important to describe the solution process.

• Computer science seeks for elegant andefficient algorithms– Algorithm: Concrete description of process.
– Algorithms lead to our modern life.

• Mathematics is vital in algorithm design– Solve seemingly-impossible tasks.

Computational Geometry• Design algorithms for geometric problems– Many modern applications• GIS, Graphics, Geometric Modeling, Robotics,Multidimensional Database, Computer Vision.

– Fast processing of massive data
• Giga pixel data = 1000,000,000 data in a single
digital picture• Elegant geometry for algorithm design– Discrete geometry, etc.
– Exciting intellectual puzzles (知的パズル）

Diverse elevation point data: density,distribution, accuracy

Photogrammetry 0.76m v. accuracy (5ft contours)

1995
Lidar 0.15m v. accuracy; altitude 700m and 2300m
1974

1999

2001

1998

RTK-GPS 0.10m v. accuracy

2004

Example of geometric computation• Convex hull computation (凸包の計算）– A showcase of algorithmic techniques• Given a set S of n points in a plane,
compute its convex hull
– Convex set: A set X such that for any twopoints p and q in X, the segment pq is in X
– Convex hull CH(S) of S : Minimum convex set
containing S• Question: Is convex hull well-defined (i.e., alwaysuniquely exists) ?

Convex Sets ?

Convex set containing S

Convex hull of S

Every convex set containing S
must also contain CH(S)Convex hull exists

CH ( S ) =I X

X : convex,X ⊃ S• Nice mathematical representation.
• But it is hard to use in computation.

Convex Hull Computation• Given a set S of n points, compute CH(S)• Can you design an algorithm?

CH ( S )=IX

X :convex , X ⊃ S

Very nuisance formula. The right hand side isintersection of infinite number of convex sets

We should transform this “cold” formula into
more “friendly” one.

Characterization.
1. CH(S) is a convex polygon
2. Vertices of CH(S) are points of S
3. CH(S) contains all points of S

Homework: Prove it!

A representation of CH(S):the list of vertices in a clockwise order
starting from the leftmost one
p9

p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5

p13
p8

Question: Show CH(S) of the above picturein the above representation.

Now, the problem is in thediscrete and finite world
p9

p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5

p13
p8

Find the (partial) permutation of S forming
the convex hull.

Verification problem
p9

p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5

p13
p8

Given a list (p1, p2,p10,p12,p9,p4), verify
whether it is CH(S).

Verification problem 1p9p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5

p13
p8

Given a list (p1, p2,p10,p12,p9,p4), verify
whether it gives a convex polygon

Verification problem 2
p9p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5

p13
p8

If the list (p1, p2,p10,p12,p9,p4) gives aconvex polygon, show all other points arecontained in it.

A brute-force algorithm• Algorithm 1:– Generate all possible partial permutations of S
– For each permutation P, verify it gives CH(S)• Questions– Is the above algorithm always correct?
– How much time does it take if n= 1000.

• Conclusion: We need a better algorithm.
• Question: Please consider a better
algorithm than this!

Analysis of Algorithm• Time Complexity–Given an input of size n (words/bits), how many basic
steps are required in an algorithm?
• Arithmetic operations• Comparisons, Data Access (read, write)• Floor/Ceiling [314.1592] = 314– T(n): number of basic steps– Asymptotic time complexity• T(n) < c f(n) for a suitable constant c and a familiar function f(n)• We write T(n) =O(f(n))• Classification of time complexity– Polynomial time algorithm: f(n) is a polynomial in n
• Linear time algorithm: T(n) = O(n)• Quadratic time algorthm: T(n) = O(n2)– Exponential time algorithm : e.g., f(n) = 2 n– Unbounded time algorithm : No such f(n)Complexity of a problem• Complexity of a problem X– The complexity of X is O(f(n)) if there is analgorithm to solve X in O(f(n)) time
– The complexity of X is Ω(f(n)) if there is noalgorithm to solve X in o(f(n)) time
• o(f(n)): strictly smaller than O(f(n))– The complexity of X is Θ（ｆ（n)) if it is both O(f(n))
and Ω(f(n))• Complexity class of a problem– A problem X is in class P if there is a polynomial
time algorithm to solve X, that is, the complexityof X = O(f(n)) for a polynomial f(n).

Typical problems in class P• Finding maximum element in a given set of nnumbers : Θ(n) time
• Sorting n numbers: O( n log n ) time– Θ(n log n) if we restrict the computation model• Computing the “distance” of two DNA sequencesof length n: O(n2) time
• Computing convex hull of n points in the plane– How to do it? What is the time complexity?

Edgeverification

p9

p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5

p13p8

•Order all points in the orthogonal direction tothe edge we want to verify• Convex hull edge if and only if its endpoints
are both maximum (or minimum) in the ordering

Edge verification
p9

p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5

p13
p8(p4, p9) is an edge of the convex hull, while(p3,p10) is not. How to distinguish them?

Convex hullalgorithm
usingedge
verification

p9p4p12p6p11p1p3p2p7p14p10p5p13p8•Verify all n(n-1)/2 candidate edges•Collect all the convex hull edges•Arrange them into convex hull
• How to do it?

Timecomplexityof thealgorithm
usingedge
verification

p9

p4

p12

p6

p11p1
p3
p2

p7

p14p10p5p13p8• O(n3) time algorithm•Edge verification = O(n) time for each candidate• O(n2) candidate edges• Polynomial time. But very slow! How to improve?

Learn fromour real life

p9p4

p12

p6

p11

p1
p3
p2

p7

p14
p10

p5p13
p8

• Consider points as pins on a board. (パチンコ台の釘だと思おう）• You are given a string. How to realize the convex
hull. (紐を使って凸包を計算しよう）• “Gift wrapping” algorithm or………

Another method
learning from ourreal life

p9

p4

p12

p6

p11

p1

p3
p2

p7

p14
p10

p5

p13p8

• Consider points as pins on a board.
• You can touch from any given direction by hand.
How to realize the convex hull.
• “hand probing” algorithm

Probing method

I love it!

p9p4

p12

p6

p11

p1
p3
p2p7

p14
p10p5

p13p8

• Consider points as pins on a board.
• You can touch from any given direction by hand tofind a vertex of the convex hull.
• “hand probing” algorithm

Hand probing
method

p9

p4

p12

p6
p1
p3
p2

p14

p11

p7
p10
p5

p13p8

• First touch with vertical lines• Next, touch with a line parallel to the one between
two vertices that we foundHand probing
methodp9p4p12p6p1
p3
p2

p7

p14

p11
p10

p5

p13
p8

Touch with a line parallel to the one between two
adjacent vertices that we foundHand probing
method

p9

p4

p12

p6
p1
p3
p2

p7

p14

p11
p10

p5

p13
p8

If we do not find a new vertex, we find an edge ofthe convex hull.

Analysis of probing algorithm• Each probe can be done in O(n) time
– Max element finding• We need at most 2h probes– h is the number of vertices in CH(P)– We find either a new vertex or a new edge

• Total time complexity O(nh)– In the worst case, O(n2)– Same as gift wrappingAlgorithmic paradigms
1. Divide and conquer
p9

p4

p12

p6

p11

p1
p3
Michael Ian Shamos

p2

p14

p7
p10
p5

p13
p8

• Process “left half” and “right half” independently• Merge two outputs

Algorithmic paradigms
2. Incremental method : Graham’s scan
p9

p4

p12

p6

p11

p1
p3
p2
Ronald Graham

p7

p14

p10
p5

p13p8

• Process points left-to-right• Start from the triangle formed by p1,p2,p3, andadd points one by one updating the convex hull

Algorithmic paradigms
2. Incremental method : Graham’s scan
p9p4

p12p6

p11

p1
p3
p2

p7p14
p10p5p13p8

Analysis of the Graham’s scan
p9

p4
p6
p1
p3
p2

p12
p11
p14

p7
p10
p5

p13

p8
When we insert a point p(k), We start from p(k-1) tofind two tangent points, and remover n(k) vertices
between two tangent points It takes O(n(k))
operations. Æ In total, O(n) operations.

Algorithmic paradigms
3. Prune by preprocessing
p9

p4

p12

p6

p11

p1
p3
p2p7p14p10p5

p13
p8• Remove all points in the pink quadrangle• Run an algorithm discussed before

Time complexities of algorithms• Brute-force: Exponential time
• Edge verification: O(n3)• Gift wrapping: O(n h)• Probing: O(n h)• Divide & Conquer: O( n log n)• Graham’s scan : O(n log n)• Pruning + Gift wrapping/Graham’s scan: ??

Applications• Classical use of convex hulls– Diameter computation• Rotating caliper– Fast collision detection• Tokuyama’s original use of convex hullalgorithms– Statistics– Data mining (!)– Image processing (!!)

Applications• Classical use of convex hulls– Diameter computation• Rotating caliper

Diameter of S = the largest distance of pairs ofpoints.
How to find it? Naively, O(n2).
We can improve it to O( n log n)

Question to students• We can compute the largest distance in S
in O( n log n) time.
• How about the shortest distance?
• Please think about it…..

Statistics• Given a histogram A, that is a sequence ofreal numbers a(1), a(2),…a(n)• Fing an increasing histogram B:b(1),b(2),..,b(n) approximating A best
– Minimizing the sum of (a(i) –b(i))2– An important operation in statistics• What is the relation to convex hull?

Statistics• Given a histogram A, that is a sequence ofreal numbers a(1), a(2),…a(n)• Fing an increasing histogram B:b(1),b(2),..,b(n) approximating A best
– Minimizing the sum of (a(i) –b(i))2– An important operation in statistics• What is the relation to convex hull?

Basic observations•

If an interval A[j,k] = a(j), a(j+1),..a(k) ofthe histogram is approximated by one
value b,b,b,b,..,b, the best value b is theaverage m(A[j,k]) of the histogram values• If the optimal increasing sequence
approximating A is b,b,b,b,..,b, theaverage of each prefix a(j), a(j+1),..,a(j+s)
cannot be smaller than m(A[j,k])– Interval averages are important.

Sequence of prefix sums
• A = a(1), a(2),.., a(n) : input histogram• sum(i) : a(1)+ a(2)+ ..+ a(i)• S = { ( i, sum(i) ): i = 1,2,..,n }• LCH(S): lower chain of CH(S)• If you list the slopes of LCH(S) at x =1.5,2.5,..,n-0.5, we obtainB= (b(i))• Isn’t it magical?

Sequence of prefix sums
• A = a(1), a(2),.., a(n) : input histogram• sum(i) : a(1)+ a(2)+ ..+ a(i)• S = { p(i) = ( i, sum(i) ): i = 1,2,..,n }• LCH(S): lower chain of CH(S)• The slope of p(j) p(k) is the average ofa(j+1), a(j+2),..,a(k)• This leads to the convex hull– Explanation: on blackboard.
– O(n) time algorithm

Approximation of curve• Input:

A piecewise linear curve y =f(x)– In an interval [0,n], with n linear pieces.

• Output: A nondecreasing curve y=g(x)• Objective: Minimize || f –g ||• Can we do this? If f(x) is a histogram, we
have done it. What is the solution in thegeneral case?
– Is O(n) time method possible?.

Unimodal approximation
Input: A histogram
Output: A histogram with one maximal peak
Objective: Minimize || f –g ||Ref 1.: J. Chun, K. Sadakane, T. Tokuyama: Linear Time Algorithm for Approximating aCurve by a Single-Peaked Curve. Algorithmica 44(2): 103-115 (2006)
Ref2: 加藤直樹他 データマイニングとその応用

K-peak approximation• Input: a piecewise function y = f(x)• Output: a function y = g(x) with at most kmaximal peaks• Objective: Minimize || f – g ||• This has applications to wave signal
processing. (Rhythm finding)