软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2008年
11期
3053-3060
,共8页
线段集合%求交查询%凸包%相交直线%线段排列
線段集閤%求交查詢%凸包%相交直線%線段排列
선단집합%구교사순%철포%상교직선%선단배렬
对给定的一个直线段集合S,研究求与S中所有直线段都相交的直线的问题.设S中的线段满足一定的不交性假设,算法可回答是否存在与S中所有线段均相交的直线的问题.如果该直线存在,则求出这样的直线的最大存在范围--啦于该范围内的每条直线都与S中的所有直线段相交.该算法的时间复杂性为O(n*log,n),应用背景是模式匹配等领域.
對給定的一箇直線段集閤S,研究求與S中所有直線段都相交的直線的問題.設S中的線段滿足一定的不交性假設,算法可迴答是否存在與S中所有線段均相交的直線的問題.如果該直線存在,則求齣這樣的直線的最大存在範圍--啦于該範圍內的每條直線都與S中的所有直線段相交.該算法的時間複雜性為O(n*log,n),應用揹景是模式匹配等領域.
대급정적일개직선단집합S,연구구여S중소유직선단도상교적직선적문제.설S중적선단만족일정적불교성가설,산법가회답시부존재여S중소유선단균상교적직선적문제.여과해직선존재,칙구출저양적직선적최대존재범위--랍우해범위내적매조직선도여S중적소유직선단상교.해산법적시간복잡성위O(n*log,n),응용배경시모식필배등영역.
