Canonical Cyclic Orderings of Point Sets in the Plane

Written by:
RR90-05

Abstract

For points in general position in the plane, we describe a family of cyclic orderings which are invariant under isometries. We prove that the family can contain at most 60 orderings. The entire family of orderings can be built in O(nlog n) time in O(n) space, where n is the number of points to be ordered. The method used to generate the cyclic orderings of points works for the vertex set of any free tree embedded in the plane. We apply the method to the Euclidean minimum spanning tree for the points in general position to obtain our family of cyclic orderings.

Related Information


Page Last Revised - October 28, 2021