census.gov Notification
Due to the lapse of federal funding, portions of this website are not being updated. Any inquiries submitted via www.census.gov will not be answered until appropriations are enacted.

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