The Table Layout Problem. Richard Anderson and Sumeet Sobti. Proceedings of the 15th Annual ACM Symposium on Computational Geometry, Miami, Florida. June 1999.

Abstract

In this paper we study a geometric problem arising in typography: the problem of laying out a two dimensional table. Each cell of the table has content associated with it. We may have choices on the geometry of cells (e.g., number of rows to use for the text in a cell.) The problem is to choose configurations for the cells to optimize an objective function such as minimum table height given a fixed width for the table.

We formulate a combinatorial version of the table layout problem, where the objective is to choose cell geometry to minimize table size. The table layout problem is NP-complete, even for very restricted instances. One of our main results is an algorithm for computing the convex hull of the set of feasible table configurations, which gives a heuristic algorithm for table layout. We establish a connection between the fractional (LP) solution to the table layout problem and generalized network flow. We also present experimental results comparing the performance of heuristics. Our final result is an algorithm for a general paragraphing problem, where we are interested in generating all minimal height-width configurations of text. We show that the set of all height-width pairs for a paragraph of $n$ words can be determined in $O^*(n^{3/2})$ time.

BibTeX Entry

@InProceedings{AS:tablelayout,
  author =    "Richard Anderson and Sumeet Sobti",
  title =     "The Table Layout Problem",
  booktitle = "Proceedings of the 15th Annual ACM Symposium on Computational Geometry, Miami, Florida",
  year =      "1999",
  month =     jun,
}

Full Paper

• PS
• PDF