The rotating caliper graph (shown above) has as its edges the
tangent pairs considered by the rotating caliper
algorithm. Equivalently an edge *xy* is in the rotating caliper graph
exactly when all input points lie between the two parallel lines through
*x* and *y* and perpendicular to *xy*.
This definition applies to arbitrary point sets, but
like the farthest point Delaunay
triangulation the rotating caliper graph only connects convex hull
vertices.

The rotating caliper graph has some interesting properties.
First, in a natural expected-case model of dynamic geometric
optimization algorithms, the expected number of RCG edges that change
per point insertion or deletion is only a small constant
(and these edges can be found quickly using some data structures
to keep track of the convex hull).
As a consequence, we can maintain the RCG itself, and the width
and diameter of the point set, in logarithmic expected time
per operation.
Second, the RCG is a *thrackle*.
This class of graph drawings, defined by John Conway,
consists of graphs in which each pair of edges has a single
intersection point (which may either be a vertex or interior
to the two edges). Conway asked whether every *n*-vertex
thrackle has at most *n* edges, and the question still
remains open if curved edges are allowed. Straight-line-segment
thrackles such as the RCG are quite well understood.

[From "Average Case Analysis of Dynamic Geometric Optimization".]

From the Geometry Junkyard,
computational
and recreational geometry.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Last update: .