Example Generators for Point Labeling

This is a description of the point set generators we offer for testing our Map Labeling algorithms. The text is an updated excerpt of the paper Map Labeling Heuristics - Provably Good and Practically Useful (Frank Wagner and Alexander Wolff, Proceedings of the 11th Annual ACM Symposium on Computational Geometry (1995) 109-118).

Random

We choose n points uniformly distributed in a square of side length 10n.

Dense

Here we randomly place as many squares of constant size as possible on a rectangle. We stop when we have unsuccessfully tried to place a new square 200 times. In a last step we assign a random corner point to each of the squares we were able to place without intersection, and return its coordinates. This method gives us a lower bound for the label size of the optimal solution. The size of the rectangle on which we place the squares is floor(a sqrt(n)) by ceil(a sqrt(n)). a is a factor chosen such that the number of successfully placed squares is approximately n, the number of sites asked for.

Hard

In principle we use the same method as for Dense, that is, trying to place as many squares as possible into a rectangle. In order to do so, we put a grid of cell size sigma on it. In a random order, we try to place a square of edge length sigma into each of the cells. This is done by randomly choosing a point within the cell and putting a fixed corner of the square on it. If it overlaps any of those chosen before, we try to place it into the same cell a constant number of times.

Real World

The municipal authorities of Munich provided us with the coordinates of roughly 1200 ground water drill holes within a 10 by 10 kilometer square centred approximately on the city centre. From this list we extract a given number of points being closest to some centre point according to the maximum norm, thus getting all those lying in a square around this extraction centre, where the size of the square depends on the number of points asked for. For our tests we chose five different centres; that of the map and those of its four quadrants in order to get results from different areas of the city with strongly varying point density. This is due to the fact that many of the holes were drilled during the construction of subway lines which are concentrated in the city centre. The whole map can be obtained as a gzipped postscript file or as a gzipped ASCII file with or without the z-coordinate of the groundlevel.

Grid

We use a grid of floor(sqrt(n)) by ceil(sqrt(n)) squares. Into each of those we randomly place a point with a certain constant offset close to one of its corners. This method also gives us a lower bound for the label size of the optimal solution.
Back to the Labeling Home Page.
Alexander Wolff