1.5-side Boundary Labeling

Boundary labeling (Bekos et al., GD 2004)

Min (total leader length or

total bend number)

s.t. #(leader crossing) = 0

1-side, 2-side, 4-side

site

label

leader

Variants

• Polygons labeling (Bekos et. al, APVIS 2006)

​

​

​

​

• Multi-stack boundary labeling (Bekos et. al, FSTTCS 2006)

1.5-side Boundary Labeling

• type-opo: direct leader vs. indirect leader

​

​

​

​

​

​

​

• Annotation system for wordprocessing S/W

direct leader

Problem Setting

• (labelSize, labelPort, Objective)

Nonuniform label

#1

#2

Uniform label

#1

#2

#3

Problem Setting

• (labelSize, labelPort, Objective)

Fixed-position port (FP)

Fixed-ratio port (FR)

Sliding port

#1

#2

#1

#2

α

α

Problem Setting

• (labelSize, labelPort, Objective)

Min (total bend num)

(TBM for short)

Min (total leader length)

(TLLM for short)

#1

#2

#3

#4

#4

#1

#2

#3

#1

#2

#3

#3

#1

#2

#(bends) = 6

#(bends) = 2

longer length

shorter length

Assumptions

• All the parameters are integers

​

• No two sites with the same x- or y- coordinate

​

• Map height = label height sum

​

• Legal leader

Our Contributions

* Pseudo-polynomial time algorithms and fixed-parameter algorithms are� designed for those intractable problems.

Solved all the problems of all the combinations of (LabelSize, LabelPort, Objective).

• Lemma 1. All direct leaders are optimal for the above concerned case.

​

​

p

U

B

p

B

U

leader l

|U|

• Theorem 2. The above case can be solved by dynamic programming in O(n⁵) time.

​

p_b

p_a

(c+b-a)-th

c-th

map

label

# = (b+a)+1

• Theorem 2. The above case can be solved by dynamic programming in O(n⁵) time.

​

p_b

p_a

(c+b-a)-th

c-th

map

label

• Theorem 2. The above case can be solved by dynamic programming in O(n⁵) time.

​

• Theorem 2. The above case can be solved by dynamic programming in O(n⁵) time.

​

Total Discrepancy Problem is NP-complete

• ∀ job J_i ∈ {J₀, J₁, …, J_2n}
• Execution time length l_i , where I₀ < I₁ < … < l_2n
• Preferred midtime M = (l₀ + l₁ + … + l_2n) /2

​

• For a planned schedule σ
• Actual midtime of J_i = m_i(σ)
• Min ( |m₀(σ) – M| + |m₁(σ) – M| + … + |m_2n(σ) – M| + |m_2n+1(σ) – M’|)

​

• Properties for the optimal schedule σ_opt
• No gaps between two jobs
• m₀(σ_opt) = M
• | {J_i : m_i < M } | = | {J_i : m_i > M } |
• σ_opt = A_n, A_n-1, …, A₁, J₀, B₁, B₂, …, B_n where {A_i, B_i} = {J_2i-1, J_2i}

J₀

J₁

J₂

J₃

J₄

• Theorem 3. Total Discrepancy Problem ≤ L(nonuniform, FR/FP/sliding, TLLM).

​

​

0

M

J₀

J₁

J₂

J₃

J₄

• Theorem 4. Subset Sum Problem ≤ L(nonuniform, FR/FP/sliding, TBM).

​

p_n+1

p_n+2

h_min

Subset Sum Problem

Input: A = {a₁, …, a_n} and� a num B = (a₁ + … + a_n)/2

​

Question: find a subset A’ ⊆ A

such that

sum(elements in A’) = B

​

​

< h_min

< h_min

h/2

• Theorem 5 (pseudo-polynomial algorithm).�The above two cases can be solved in O(n⁴h) time, where h is the map height.

​

S(a, b, t ) =

S(a, b, c) =

// all direct leaders

// downward indirect leader

// upward indirect leader

// the solution of the problem with p_a, p_a+1, …, p_b connected to label positions c to c+(b-a)+1

// the solution of the problem with p_a, p_a+1, …, p_b connected to y-coordinate t

(uniform label case)

• Theorem 6 (fixed-parameter algorithm).�The above two cases using k different label heights can be solved in O(n^k+4) time.

​

• Theorem 5. The above two cases can be solved in O(n⁴h) time.
• Lemma 2. num( positions of each label using k different label heights ) = O(n^k).

pf.

• Induction on k
• Assume num(…(k-1) …) = O(n^k-1)
• Consider each label, which is the i-th label from the bottom

​

​

h = n^k

O(n^k-1) positions

at most O(n)

Conclusion

* Pseudo-polynomial algorithms and fixed-parameter algorithms are� designed for those intractable problems.

Solved all the problems of all the combinations of (LabelSize, LabelPort, Objective).