%0 Journal Article
%T Computing Lines Intersecting with Set of Line Segments and the Maximum Range<br>计算线段集合的相交直线及其最大存在范围
%A WANG Jia-Ye
%A YANG Cheng-Lei
%A ZHANG Cai-Ming
%A <br>汪嘉业
%A 杨承磊
%A 张彩明
%J 软件学报
%D 2008
%I 
%X For a given set S of line segments, finding a straight line intersecting with all the line segments in S is studied in this paper. If an intersection restriction is satisfied by the set, the algorithm presented is to answer whether there is a straight line intersecting with all the line segments in S. If the straight lines exist, the algorithm finds a maximum range, where every straight line located in the range intersects with all the line segments in S. The time complexity of the algorithm is O(n×log n). The algorithm can be used in pattern marching and so on.
%K line segment set
%K query intersection
%K convex hull
%K intersecting straight line
%K arrangement of line segments<br>线段集合
%K 求交查询
%K 凸包
%K 相交直线
%K 线段排列
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=A9696652BF421CA6F8089734D9A0F12D&yid=67289AFF6305E306&vid=2A8D03AD8076A2E3&iid=708DD6B15D2464E8&sid=29A94D7BA68AD64A&eid=3460121FD3CDE493&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=6