Approximating text by its area
Nathan Hurst, Kim Marriott · 2007
Given possibly non-rectangular shapes, S1, ..., Sn, and some English text, T, we give methods based on approximating T by its area that determine for each Si whether T definitely fits in Si, definitely does not fit in Si, or probably fits in Si. These methods have complexity linear in the size of Si, assuming it is represented as a trapezoid list, but do not depend on the size of T. They require a linear time shape independent pre-processing of the text.