计算线段集合的相交直线及其最大存在范围

• 作者: 张彩明 杨承磊 汪嘉业
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 线段集合 求交查询 凸包 相交直线 线段排列
• 年，卷（期）: 2008,（11）
• 所属期刊栏目: 计算机图形学与计算机辅助设计
• 页码范围: 3053-3060
• 页数: 8页
• 分类号: TP391
• 字数: 3720字
• 语种: 中文

摘要

对给定的一个直线段集合S,研究求与S中所有直线段都相交的直线的问题.设S中的线段满足一定的不交性假设,算法可回答是否存在与S中所有线段均相交的直线的问题.如果该直线存在,则求出这样的直线的最大存在范围--啦于该范围内的每条直线都与S中的所有直线段相交.该算法的时间复杂性为O(n*log,n),应用背景是模式匹配等领域.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张彩明	山东大学计算机科学与技术学院	103	1058	18.0	27.0
2	杨承磊	山东大学计算机科学与技术学院	34	356	10.0	18.0
3	汪嘉业		1	0	0.0	0.0