Block sorting is used in connection with Optical Character Recognition (OCR). Recent work has focused on finding good strategies which work in practice. In this paper, we show that optimizing block sorting is -hard. Along with this result, we give new non-trivial lower bounds. These bound can be computed efficiently. We define the concept of "Local Property Algorithms" and show that several previously published block sorting algorithms fall into this class.
['Wolfgang W. Bein', 'Lawrence L. Larmore', 'Shahram Latifi', 'I. Hal Sudborough']
Block Sorting is Hard