On sequential shape descriptions

摘要

Given a shape, we wish to describe it as the union and/or difference of primitive, possibly parameterized, shapes that constitute an alphabet. We would like this description to be ordered such that “most” of the description is conveyed within the first few terms of the description. In other words, we want as small an error as possible for any possible truncation of a description. We present a new criterion for evaluating such sequential descriptions.For the specific case of right-angled, or rectilinear, polygons in a plane, and using only a rectangle as the primitive shape, we present an algorithm for finding optimal sequential descriptions. Though the running time of this algorithm is exponential in the worst case, we show how running time can be traded off against optimality, and how “reasonable” solutions can be found quickly.