We study three orientation-based shape descriptors on a set of continuously moving points P : the first principal component, the smallest oriented bounding box and the thinnest strip. Each of these shape descriptors essentially defines a cost capturing the quality of the descriptor (sum of squared distances for principal component, area for oriented bounding box, and width for strip), and uses the orientation that minimizes the cost. This optimal orientation may be very unstable as the points are moving, which is undesirable in many practical scenarios. Alternatively, we can bound the speed with which the orientation of the descriptor may change . However, this can increase the cost (and hence lower the quality ) of the resulting shape descriptor. In this paper we study the trade-off between stability and quality of these shape descriptors. \% We first show that there is no stateless algorithm, which depends only on the input points in one timestep and not on previous states , that both approximates the minimum cost of a shape descriptor and achieves bounded speed . On the other hand, if we can use the previous state of the shape descriptor to compute the new state, then we can define "chasing" algorithms that attempt to follow the optimal orientation with bounded speed. Under mild conditions, we show that chasing algorithms with sufficient bounded speed approximate the optimal cost at every time step for oriented bounding boxes and strips , but not for principal components . The analysis of such chasing algorithms is challenging and has received little attention in literature, hence we believe that our methods used to perform this analysis are of independent interest.
We study three orientation-based shape descriptors on a set of continuously moving points : the first principal component, the smallest oriented bounding box and the thinnest strip. Each of these shape descriptors essentially defines a cost capturing the quality of the descriptor and uses the orientation that minimizes the cost. This optimal orientation may be very unstable as the points are moving, which is undesirable in many practical scenarios. If we bound the speed with which the orientation of the descriptor may change , this may lower the quality of the resulting shape descriptor. In this paper we study the trade-off between stability and quality of these shape descriptors. We first show that there is no stateless algorithm, an algorithm that keeps no state over time , that both approximates the minimum cost of a shape descriptor and achieves continuous motion for the shape descriptor . On the other hand, if we can use the previous state of the shape descriptor to compute the new state, we can define "chasing" algorithms that attempt to follow the optimal orientation with bounded speed. We show that, under mild conditions, chasing algorithms with sufficient bounded speed approximate the optimal cost at all times for oriented bounding boxes and strips . The analysis of such chasing algorithms is challenging and has received little attention in literature, hence we believe that our methods used in this analysis are of independent interest.
D
P
R
(sum of squared distances for principal component, area for oriented bounding box, and width for strip), and
and
R
Alternatively, we can
If we
R
. However, this can increase the cost (and hence
, this may
D
)
D
\%
R
which depends only on the input points in one timestep and not on previous states
an algorithm that keeps no state over time
R
bounded speed
continuous motion for the shape descriptor
D
then
R
Under
We show that, under
D
we show that
R
every time step
all times
D
, but not for principal components
R
to perform
in