Crossing-Free�Boundary Labeling�Using Hyperleaders

Chun-Cheng Lin

​

Taipei Municipal University of Education

Outline

• Introduction

​

• Motivations

​

• Our results
• One-side case 🡪 O(n log n) time solvable
• Two-side case 🡪 O(n²) time solvable
• Four-side case 🡪 simulated annealing

​

• Conclusion & Future work

2

Map Labeling

3

Boundary Labeling [Bekos et al., GD 2004]

4

Min (total leader length)

s.t. #(leader crossing) = 0

1-side, 2-side, 4-side

site

label

leader

Variants

• Polygons labeling

​

​

​

​

• Multi-stack boundary labeling

5

• Type-od leader

​

​

• Type-pd leader

• Type-do leader

5

Many-Site-to-One-Label Boundary Labeling�(a.k.a., Many-to-One Boundary Labeling)�(Lin, Kao Yen, 2008)

6

Brown booby

Taiwan hill partridge

Masked palm civet

Hawk

Melogale moschata

Bamboo partridge

Chinese pangolin

Mallard

​

Distribution of some

animals in Taiwan:

Two-Side Many-to-One Boundary Labeling

7

One More Example�– Server Motherboard –

8

Many-to-One Boundary Labeling�Using Hyperleaders & Dummy Labels

• Type-opo hyperleaders & dummy labels

​

​

​

​

​

• Main features
• No confusion and crossings between leaders
• Suitable for labeling the sites with clusters
• One-side and two-side cases are suitable for the maps with vertical-strip shapes

9

R

Track Routing Area

l₁’

l₁

l₂

No leader crossings

adding

dummy

labels

dummy

label

Our Concerned Problem

• Minimizing the number of dummy labels

s.t. there are no leader crossings.

Furthermore, after determining # & pos of dummy labels,

the number of bends is minimized;

the total leader length is minimized.

​

10

R

Our Theoretical Results for Many-to-One Boundary Labeling

11

Note that c is a number depending on the sum of edge weights.

12

R

R

R

g₁

g₂

g₃

g₄

g₅

g₆

g₇

g₈

R

g₁

g₂

g₃

g₄

g₅

g₆

g₇

g₈

l₁

l₂

l₃

l₄

l₅

l₆

l₇

l₈

One-Side Case

Input

Step 1.

Step 2.

Observation. Only the order of y-coordinates of sites matters.

Step 3.

How to Route Hyperleaders?

13

ε

R

g_i

l_i-1

l_i

R

g_i

l_i-1

l_i

y_p(l_i)

R

g_i

l_i

l_i+1

y_p(l_i)

R

g_i

l_i

R

g_i

l_i

ε

y_p(l_i)

Push i to stack S.

(the routing of g_i is determined after the routing of g_i+1 is determined)

R

g_i

l_i

l_i+1

y_p(l_i)

R

ε

g_i

l_i

l_i+1

ε

R

g_i

l_i-1

l_i

R

g_i

l_i-1

l_i

y_p(l_i)

ε

R

g_i

l_i

l_i+1

ε

Two-Side Case

L

Step 1.

Step 2.

R

Scan from the top to the bottom.

Each label is placed on the right

or the left line.

If moving labels in L to R does not result in any dummy label, the concerned label is placed on the same line as its guy; o.w. ...

its recently

shown guy.

the concerned label

R

g₁

g₂

g₃

g₄

g₅

g₆

g₇

g₈

14

An Example

15

An Example (cont.)

16

Many-to-One Boundary Labeling

• The original

​

​

​

​

​

​

• New

​

17

Our Results

18

^* Note that n is the number of sites.

Four-side case

• [Bekos et al., 2007]
• Determining which sites are connected to one of the four sides so that the objective is achieved leads to the NP-hard Partition problem

​

• Use the simulated annealing (SA) to solve the four-side case

​

​

19

Simulated Annealing for 4-side case

• Configuration
• Corresponded to a site p
• Site p divides the map into four regions A₁-A₄

​

• Initial configuration
• A configuration where the sites in each region are as equal as possible

​

• Neighbor
• Randomly select a corner c of the map
• Rotate the line connected to c around c in counterclockwise direction
• The configuration corresponding to the first scanned site is selected as the neighbor

​

• Energy cost function =

​

​

• The cooling schedule is based on the previous work

20

p

λ (normalized # of dummy labels) + (1-λ)(normalized total leader length)

c

Statistics

21

Experimental Results (I)

22

Experimental Results (II)

23

A Practical Example

24

Conclusion

• Crossing-free many-to-one boundary labeling using hyperleaders (and dummy labels)
• 1-side case 🡪 O(n log n) time for dummy label min. problem
• 2-side case 🡪 O(n²) time for dummy label min. problem
• 4-side case 🡪 simulated annealing

​

25

Future work

• Considering other kinds of leaders

26

R

l₁

l₂

l₃

l₄

l₅

R

l₁

l₂

l₃

l₄

l₅

R

l₁

l₂

l₃

l₄

l₅

MST

Steiner Tree

Steiner

points

Thank you for your attention!