Abstract
在本篇論文裡我們研究計算機何上相交的問題，我們給一個O （N log N ）以找N 條水平垂直線段中連接單元的演算法，接著是一個以O （N log N ＋K ）找出圓內N 條弦所有相交對的演算法，而且我們也證圓內N 條弦的連接單元亦可在O （N log N ）時間內找到，上述三演算法皆使用O （n ）記憶體且可證明是最佳解，最後我們再證明圓內N 條可轉換成3N條正交線段，因此用以解水平垂直線段問題的演算法也可解圓內弦的問題。
- Title
- 線段之連接及相交演算法之研究
- Translated title
- 線段之連接及相交演算法之研究
- Creators
- 歐陽永文 (Author)
- Contributors
- 楊熙年 (Advisor)
- Awarding Institution
- National Tsing Hua University; Masters
- Theses and Dissertations
- Masters, National Tsing Hua University
- Resource Type
- Thesis
- Language
- English