%0 Journal Article
%T 计算线段集合的相交直线及其最大存在范围
%A 张彩明
%A 杨承磊
%A 汪嘉业
%J -
%D 2008
%X 对给定的一个直线段集合S,研究求与S中所有直线段都相交的直线的问题.设S中的线段满足一定的不交性假设,算法可回答是否存在与S中所有线段均相交的直线的问题.如果该直线存在,则求出这样的直线的最大存在范围——位于该范围内的每条直线都与S中的所有直线段相交.该算法的时间复杂性为O(n*log n),应用背景是模式匹配等领域
%K 线段集合 求交查询 凸包 相交直线 线段排列
%U http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=20081126&flag=1