Fitting a two-joint orthogonal chain to a point set

Description

We study the problem of fitting a two-joint orthogonal polygonal chain to a set S of n points in the plane, where the objective function is to minimize the maximum orthogonal distance from S to the chain. We show that this problem can be solved in Θ(n) time if the orientation of the chain is fixed, and in Θ(n logn) time when the orientation is not a priori known. Moreover, our algorithm can be used to maintain the rectilinear convex hull of S while rotating the coordinate system in O(n logn) time and O(n) space, improving on a recent result (Bae et al., 2009 [4]). We also consider some variations of the problem in three-dimensions where a polygonal chain is interpreted as a configuration of orthogonal planes. In this case we obtain O(n), O(n logn), and O(n2) time algorithms depending on which plane orientations are fixed.

Abstract

Open archive-Elsevier

Additional details