# Chapter 5 Guillotine Cut - personal.utdallas.edu Chapter 5 Guillotine Cut (2) Portals Ding-Zhu Du Rectilinear Steiner Tree Given a set of points in the rectilinear plane, find a minimum length tree interconnecting them. Those given points are called terminals.

Initially Edge length < RSMT Initially L n = # of terminals 2

2 n x n grid Total moving Length: L L n 2

n n If PTAS exists for grid points, then it exists for general case. (1/3-2/3)-cut 1/3 Shorter edge Longer edge

> 1/3 2/3 Longer edge Cut line position L

2 2 n x n grid Cut line always passes through the center of a cell.

1 ( assume) Depth of (1/3-2/3)-cut Note that every two parallel cut lines has distance at least one. Therefore, the smallest rectangle has area 1. After one cut, each resulting rectangle has area Within a factor of 2/3 from the original one. Hence, depth of cuts < (4 log n)/(log (3/2)) = O(log n)

since depth 4 (2/3) n >1 (1/3-2/3)-Partition O(log n) Portals

m portals divide a cut segment equally. Restriction A rectilinear Steiner tree T is restricted if there exists a (1/3-2/3)-partition such that If a segment of T passes through a cut Line, it passes at a portal. Minimum Restricted RST can be

26 O(m) computed in time n 2 by dynamic programming 2 Choices of each cut line = O(n ) 24 O(m) # of subproblems = n 2

# of subproblem Each subproblems can be described by three facts: 1. Position of for edges of a rectangle. 2. Position of portals at each edge. 3. Set of using portals. O(n 8 ) 4 O(n ) 2

O(m) 4. Partition of using portals on the boundary. (In each part of the partition, all portals are connected and every terminal inside of the rectangle is connected to some tree containing a portal. ) 2 O(m)

Position of portals O(n2 ) O(n 2 ) # of partitions N(k) = # of partitions

N(0)=1 N(k) = N(k-1) + N(k-2)N(1) + + N(1)N(k-2) + N(k-1) = N(k-1)N(0) + N(k-2)N(1) + + N(0)N(k-1) 2 k f(x) = N(0) + N(1)x + N(2)x + + N(k)x +

1 k 2 xf(x) = f(x) - 1 1 1 4x f ( x)

. 2x Since f (0) 1, we have 1/ 2 1 1 4x ( 4 x) k /( 2 x) f ( x)

2x k 1 k 1/ 2 k 1 ( 4) / 2 N (k ) k 1 0.5(0.5 1)(0.5 2) (0.5 k ) k

2 k 1 ( 1) 2 (k 1) 2O ( k ) Analysis (idea) Consider a MRST T. Choose a (1/3-2/3)-partition. Modify it into a restricted RST by moving

cross-points to portals. Estimate the total cost of moving crosspoints. Choice of (1/3-2/3)-partition 1/3 2/3 Each cut is chosen to minimize # of cross-points. (# of cross-points) x (1/3 longer edge length)

< (length of T lying in rectangle). Moving cross-points to portals Cost = (# of cross-points) x ( edge length/(m+1)) < (3/(m+1)) x (length of T lying in rectangle) Moving cost at each level of (1/3-2/3)-Partition < (3/(m+1)) x (length of T ) O(log n)

Total cost < O(log n)(3 / (m+1)) x (length of T) Choose m = (1/) O(log n). Then 2 O(m) O(1/) =n .

RSMT has (1+)-approximation with running O(1/) Time n . Thanks, End