Finding adjacencies in non-overlapping polygons
Adler, J; Christelis, GD; Deneys, JA; Konidaris, GD; Lewis, G; Lipson, AG; Phillips, RL; Scott-Dawkins, DK; Shell, DA; Strydom, BV; Trakman, WM; Van Gool, LD
Date:
2001
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.
Citation:
Adler, J., Christelis, G.D., Deneys, J.A., Konidaris, G.D., Lewis, G., Lipson, A.G., Phillips, R.L., Scott-Dawkins, D.K., Shell, D.A., Strydom, B.V., Trakman, W.M. & van Gool, L.D. (2001) Finding adjacencies in non-overlapping polygons. Hardware, Software and Peopleware: Proceedings of the Annual Conference of the South African Institute of Computer Scientists and Information Technologists, University of South Africa, Pretoria, 25-28 September 200
Show full item record
Files in this item
Copyright Statement
Items in UNISA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated. Items may only be viewed and downloaded for private research and study purposes. Please acknowledge publications according to acceptable standards and norms.
This item appears in the following Collection(s)
