單一直線地圖標記點數最佳化

Abstract

在這篇論文裡，我們主要探討的是地圖標記的問題，而且所有需要被標記的點都限制在單一直線上。

已經眾所皆知的是，在提供了已排序的點集的前提下，1d4P矩形標籤、1d4S方形標籤以及Slope4P固定高度(寬度)的標籤放置問題都可以在線性的時間內解決。

我們在這篇論文中將原本「判斷版本」的結果擴展到「最佳化版本」：也就是Max-1d4P的標籤放置問題，它將會從給定在水平線上的所有點中找出在不違反規則的前提下最多可標記的點數。

我們將會提供一個O(n log n)的演算法，這裡的n是所輸入的點數。

In this paper, we consider a map labeling problem where the anchors to be labeled are restricted on a line. It is known that the 1d4P rectangle label, the 1d4S square label and the Slope4P ?xed height (width) label placement problems can all be solved in linear time provided that the anchors are in sorted order. We extend the decision version results to the maximization version: Max-1d4P label placement problem, which is to maximize the number of labels that can be placed on a given set of anchors on a horizontal line. We present an O(n log n) time algorithm solution, where n is the input size.