Reporting the crossing-free segments of a complete geometric graph

摘要

A complete geometric graph is a pair (S,E), where S = {p1#x2026;pn} is a set of n points in general position on the Euclidean plane andEthe set of all closed line segments whose endpoints are inS. A closed segmente(s,t) frompstoptis crossing-free, ife(s, t) does not cross any segment inE. In this paper, we will propose an algorithm that reports all crossing-free segments of (S,E) in0(n2) time.