Label placement plays an important role in information visualization. On maps, diagrams, and graphs, properly placed text labels clarify the meaning of a point, a line, or an area. It is known that placing labels is a costly part in a map making process. Many researchers in cartography and computational geometry have suggested various models and solutions.
In spite of the importance, most label placement problems are proved NP-hard. Therefore, one should consider an approximate solution instead of exact solution. An approximation algorithm guarantees that its solution is always near the exact solution. For example, in maximization problem, ε-approximation algorithm guarantees that the solution is greater than the exact solution over ε.(ε > 1)
The models of label placement defined can be classified by several ways: the feature to be labeled, the maximization objective, the shape of labels, the placement restriction, the number of labels for each feature, and so on.
In this thesis, we consider the size maximization problem of axis-parallel rectangular and square labels placed on points. First, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. Formann and Wagner showed that this problem is NP-complete and there is no polynomial time algorithm less than 2-approximation unless P = NP[12]. We present a 2-pproximation algorithm of the non-uniform rectangle case which runs in $O(n^2log n)$ time and takes $O(n^2)$ space. We also show that the decision problem can be solved in O(nlog n) time and space.
We also propose a label placement model, called 8-position model, that the label can be placed among up, down, right, left, upper-right, upper-left, lower-right and lower left of the point. We consider the label placement with uniform squares, and present a 2-approximation algorithm that takes O(nlog n) time. This algorithm is 3-approximation on the 4-slider model, which allows the squares to be placed in order that the point lies on the boundary of the square. Finally, we show that there is no polynomial time algorithm less than 1.5-approximation on 8-position model unless P = NP.
정보를 시각화함에 있어서 명칭배치는 중요한 역할을 한다. 명칭, 즉 문자 라벨은 지도, 도면, 그래프 상의 점, 선, 영역이 어떤 의미를 갖는지 알려준다. 만약 라벨이 없다면 그 의미를 파악하기 어렵다. 그러나, 지도를 제작함에 있어서 라벨 배치는 가장 비용이 많이 드는 부분으로 알려졌고, 따라서, 효율적인 라벨 배치는 지도학자들의 관심대상이다.
이러한 중요성에도 불구하고 라벨 배치 문제는 대부분의 경우 NP-hard임이 증명되었다. 따라서, 이와 같은 문제를 해결하려면 휴리스틱이나 전문가 시스템과 같은 인공지능적 방법이나 근사 알고리즘과 같은 알고리즘적인 접근법을 고려하여야 한다. 근사 알고리즘이란, 출력되는 값이 최적 값에 가까움을 보장하는 알고리즘이다. 예를 들어, 최대화 문제에서는 ε-근사 알고리즘은 최적인 답의 ε분의 일보다 크다는 것을 보장하는 알고리즘이다.(ε>1)
라벨 배치 문제를 정형화 하기 위해서 여러가지 라벨 배치 모델이 제안되어 왔다. 라벨 배치 모델은 라벨이 붙여질 객체의 종류, 최대화 기준, 라벨의 모양, 라벨 배치 제한, 한 객체에 배치할 라벨의 갯수 등의 기준에 따라 나눌 수 있다.
본 논문에서는 점 객체에 대해서 되도록이면 큰 직사각형 혹은 정사각형 라벨을 배치하는 근사 알고리즘을 제시한다. 먼저, 점집합과 그 점에 하나씩 임의의 크기의 직사각형이 주어졌을때 직사각형의 꼭지점에 점이 위치하도록 직사각형을 배치하는 문제를 고려한다. Formann과 Wagner는 이 문제가 NP-complete이고, P = NP가 아닌 이상 근사율 2 미만의 근사 알고리즘이 존재하지 않는다는 것을 증명하였다. 본 논문에서는 2-근사 알고리즘을 제시한다. 먼저, $O(n^2log n)$ 의 시간과 $O(n^2)$ 의 공간을 사용하는 최적화 알고리즘을 제시하고, O(nlog n)의 시간과 O(n)의 공간을 사용하는 효율적인 결정 알고리즘을 제시한다.
본 논문에서는, 또한, 점 객체의 상, 하, 좌, 우, 좌상, 좌하, 우상, 우하에 정사각형이 배치되는 8-위치(8-position) 모델을 제시한다. 먼저, O(nlog n)시간을 사용하는 2-근사 알고리즘을 제시한다. 다음에는 정사각형의 변에 점 객체가 위치하도록 정사각형을 배치하는 미닫이 모델 (4-slider model)에서, 위의 알고리즘이 3-근사 알고리즘이라는 것을 보인다. 마지막으로, p≠NP 라면, 8-위치 모델에서 1.5미만의 근사율을 갖는 근사 알고리즘이 존재하기 않는다는 것을 보인다.
