Hints for the Use of Map Labeling Heuristics
We offer you a choice of
example generators
and
Map Labeling algorithms
. The following remarks are intended to help you to make some observations during testing.
Some people have complained that the indices attached to say small random examples did overlap. However this is only the case in the display of the newly generated point set. You must then chose one of the algorithms offered below, and press the
Submit Query
button to have the instance labeled properly. The indices shown initially are all just placed above the sites. They are meant to help you to find the coordinates of a site in the INPUT field, so that you can change the position of a specific site. For reasons of legibility, these indices are only displayed for small problem sizes.
Some brousers (netscape for instance) cause problems with input via TEXTAREA, so we used an INPUT field in the FORM in which we ask you for coordinates. If you fill in your own ones, make sure they are seperated by blanks - not carriage returns.
Approximation Algorithm
A
normally produces results which are only slightly better than 50% of the
optimal solution
. This is intolarably bad in practice. On the other hand twice the label size found by
A
gives a good upper bound for the
optimal size
. This is important to estimate the quality of the heuristics for large point sets where the exact solvers either run out of memory or need ages to come up with the optimal solution.
To see the differences between the
heuristics
, use
dense
and
hard
examples for your tests. On
random
and
real world
problems they all find solutions very close to 100% of the optimal label size. This of course is an interesting fact in its own right.
Large
grid
examples even bring
Approximation Algorithm
B
down to solutions no better than its quality guaranty of 50% of the optimal solution.
Back to the
Labeling Home Page
.
Alexander Wolff
