Abstract
於1985年，Lee 與Chin提出：找出n 條線的交點凸集（Convex hull ）而僅需O (nlog n)的預估時間（time-complexity ）之後，而一有興趣的問題，而n 個點的某一問題需f (n) 的預估時間，據有一些性質的n2個點，在同一問題上，是否也需f (n2)的預估時間。在本篇文章裡，我們使用掃描線（Line-sweep）的技巧，並利用平橫樹（Balanced-tree）的資料結構而僅需O (c n log n）的預估時間。在本文中，我們使用O (c n log n）的預估時間來解決給定c 個方向的線段交點凸集問題，因此關於在給定c 個方向的線段交點上之一些問題也可以預估時間O (c n logn ）內解決，例如在給定c 個方向的線段交點裡，找出相距最遠的兩交點，或者找出最小的圓包圍這些交點等問題。