Partial construction of an arrangement of lines and its application to optimal partitioning of bichromatic point set

金沢大学This paper presents an efficient algorithm for construction at-most-k levels of an arrangement of n lines in the plane in ime O(nk + nlogn), which is optimal since Ω(nk) line segments are included there. The algorithm can sweep the at-most-k levels of the arrangement using O(n) space. Although Everett recently gave an algorithm for constructing the at-most-k levels with the same time complexity independently, our algorithm is superior with respect to the space complexity as a sweep algorithm. Then, we apply the algorithm to a bipartitioning problem of a bichromatic point set