Partial construction of an arrangement of lines and its application to optimal partitioning of bichromatic point set
Tetsuo Asano, Takeshi Tokuyama, 哲夫 浅野 · Institutional Repositories DataBase (IRDB) · 1994
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.