Institutional Repository

Finding adjacencies in non-overlapping polygons

Show simple item record 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
dc.contributor.editor Renaud, K.
dc.contributor.editor Kotze, P
dc.contributor.editor Barnard, A 2018-08-23T08:11:30Z 2018-08-23T08:11:30Z 2001
dc.identifier.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 en
dc.identifier.isbn 1-86888-195-4
dc.description.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. en
dc.language.iso en en
dc.title Finding adjacencies in non-overlapping polygons en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account