Reporting the crossing-free segments of a complete geometric graph

Abstract

A complete geometric graph is a pair (S,E), where S = {p ₁…p_n } is a set of n points in general position on the Euclidean plane and E the set of all closed line segments whose endpoints are in S. A closed segment e(s,t) from p_s to p_t is crossing-free, if e(s, t) does not cross any segment in E. In this paper, we will propose an algorithm that reports all crossing-free segments of (S,E) in 0(n ²) time.

Keywords:

• Computational geometry
• geometric intersection problem
• geometric graph
• angular sort

C.R. Categories:

• I3
• G2