Stabbers of line segments in the plane |
| |
Authors: | Mercè Claverol Delia Garijo Clara I Grima Alberto Márquez Carlos Seara |
| |
Institution: | a Dpt. de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Spain b Dpto. de Matemática Aplicada I, Universidad de Sevilla, Sevilla, Spain c Dpt. de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Spain |
| |
Abstract: | The problem of computing a representation of the stabbing lines of a set S of segments in the plane was solved by Edelsbrunner et al. We provide efficient algorithms for the following problems: computing the stabbing wedges for S, finding a stabbing wedge for a set of parallel segments with equal length, and computing other stabbers for S such as a double-wedge and a zigzag. The time and space complexities of the algorithms depend on the number of combinatorially different extreme lines, critical lines, and the number of different slopes that appear in S. |
| |
Keywords: | Stabbers Transversal Line segments Red-blue separability |
本文献已被 ScienceDirect 等数据库收录! |
|