The Minimum Distance Intersection Graph of a Finite Planar Set
이상호, 이수원, 좌경룡 · 1983
A new graph, called the minimum distance intersection graph (MDIG(λ)), is defined on a set of points in the Euclidean plane. Some characteristics of MDIG(λ) are examined, and it is shown that MDIG(λ) has at most O(n) edges. Also, it is found that MDIG(λ) can be constructed in O(n log n) time by using Bentley and Ottmann's algorithm.