Finding adjacencies in non-overlapping polygons

Abstract

Two polygons are adjacent if they have edges which share a common edge segment. In this paper we consider the problem of finding adjacencies in a set of n non-overlapping polygons. Using the fact that adjacent edges must lie on the same line, an algorithm with time complexity E>(z log z) (where z is the total number of edges) is derived. Thereafter, we consider the particular case where the polygons are convex, as this has practical applications. Using the properties of convex polygons, we derive a more efficient algorithm with time complexity E>(z Jog n). Both algorithms are proved to be correct and their optimality is discussed.