Partial Construction of an Arrangement of Lines and Its Application to Optimal Partitioning of Bichromatic Point Set

Tetsuo ASANO; Takeshi TOKUYAMA

Partial Construction of an Arrangement of Lines and Its Application to Optimal Partitioning of Bichromatic Point Set

Tetsuo ASANO, Takeshi TOKUYAMA

Full Text Views

0

Share
Cite this

Summary :

This paper presents an efficient algorithm for constructing at-most-k levels of an arrangement of n lines in the plane in time O(nk+n log n), 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 et al. 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： For r red points and b blue points in the plane and a directed line L, the figure of demerit f_d(L) associated with L is defined to be the sum of the number of blue points below L and that of red ones above L. The problem we are going to consider is to find an optimal partitioning line to minimize the figure of demerit. Given a number k, our algorithm first determines whether there is a line whose figure of demerit is at most k, and further finds an optimal bipartitioning line if there is one. It runs in O(kn+n log n) time (n=r+b), which is subquadratic if k is sublinear.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.4 pp.595-600

Publication Date: 1994/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Tetsuo ASANO, Takeshi TOKUYAMA, "Partial Construction of an Arrangement of Lines and Its Application to Optimal Partitioning of Bichromatic Point Set" in IEICE TRANSACTIONS on Fundamentals, vol. E77-A, no. 4, pp. 595-600, April 1994, doi: .
Abstract: This paper presents an efficient algorithm for constructing at-most-k levels of an arrangement of n lines in the plane in time O(nk+n log n), 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 et al. 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： For r red points and b blue points in the plane and a directed line L, the figure of demerit f_d(L) associated with L is defined to be the sum of the number of blue points below L and that of red ones above L. The problem we are going to consider is to find an optimal partitioning line to minimize the figure of demerit. Given a number k, our algorithm first determines whether there is a line whose figure of demerit is at most k, and further finds an optimal bipartitioning line if there is one. It runs in O(kn+n log n) time (n=r+b), which is subquadratic if k is sublinear.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e77-a_4_595/_p

Copy

@ARTICLE{e77-a_4_595,
author={Tetsuo ASANO, Takeshi TOKUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Partial Construction of an Arrangement of Lines and Its Application to Optimal Partitioning of Bichromatic Point Set},
year={1994},
volume={E77-A},
number={4},
pages={595-600},
abstract={This paper presents an efficient algorithm for constructing at-most-k levels of an arrangement of n lines in the plane in time O(nk+n log n), 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 et al. 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： For r red points and b blue points in the plane and a directed line L, the figure of demerit f_d(L) associated with L is defined to be the sum of the number of blue points below L and that of red ones above L. The problem we are going to consider is to find an optimal partitioning line to minimize the figure of demerit. Given a number k, our algorithm first determines whether there is a line whose figure of demerit is at most k, and further finds an optimal bipartitioning line if there is one. It runs in O(kn+n log n) time (n=r+b), which is subquadratic if k is sublinear.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Partial Construction of an Arrangement of Lines and Its Application to Optimal Partitioning of Bichromatic Point Set
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 595
EP - 600
AU - Tetsuo ASANO
AU - Takeshi TOKUYAMA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1994
AB - This paper presents an efficient algorithm for constructing at-most-k levels of an arrangement of n lines in the plane in time O(nk+n log n), 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 et al. 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： For r red points and b blue points in the plane and a directed line L, the figure of demerit f_d(L) associated with L is defined to be the sum of the number of blue points below L and that of red ones above L. The problem we are going to consider is to find an optimal partitioning line to minimize the figure of demerit. Given a number k, our algorithm first determines whether there is a line whose figure of demerit is at most k, and further finds an optimal bipartitioning line if there is one. It runs in O(kn+n log n) time (n=r+b), which is subquadratic if k is sublinear.
ER -