Person:

Shieber, Stuart

A major factor affecting the clarity of graphical displays that include text labels is the degree to which labels obscure display features (including other labels) as a result of spatial overlap. Point-feature label placement (PFLP) is the problem of placing text labels adjacent to point features on a map or diagram so as to maximize legibility. This problem occurs frequently in the production of many types of informational graphics, though it arises most often in automated cartography. In this paper we present a comprehensive treatment of the PFLP problem, viewed as a type of combinatorial optimization problem. Complexity analysis reveals that the basic PFLP problem and most interesting variants of it are NP-hard. These negative results help inform a survey of previously reported algorithms for PFLP; not surprisingly, all such algorithms either have exponential time complexity or are incomplete. To solve the PFLP problem in practice, then, we must rely on good heuristic methods. We propose two new methods, one based on a discrete form of gradient descent, the other on simulated annealing, and report on a series of empirical tests comparing these and the other known algorithms for the problem. Based on this study, the first to be conducted, we identify the best approaches as a function of available computation time.

The ability to recognize regions in a bitmap image has applications in various areas, from document recognition of scanned building floor plans to processing of scanned forms. We consider the use of deformable polygons for delineating partially or fully bounded regions of a scanned bitmap that depicts a building floor plan. We discuss a semi-automated interactive system, in which a user positions a seed polygon in an area of interest in the image. The computer then expands and deforms the polygon in an attempt to minimize an energy function that is defined so that configurations with minimum energy tend to match the subjective boundaries of regions in the image. When the deformation process is completed, the user may edit the deformed polygon to make it conform more closely to the desired region. In contrast to area-filling techniques for delineating areal regions of images, our approach works robustly for partially bounded regions.

Abstract: In spite of great advances in the automatic drawing of medium and large graphs, the tools available for drawing small graphs exquisitely (that is, with the aesthetics commonly found in professional publications and presentations) are still very primitive. Commercial tools, e.g., Claris Draw, provide minimal support for aesthetic graph layout. At the other extreme, research prototypes based on constraint methods are overly general for graph drawing. Our system improves on general constraint-based approaches to drawing and layout by supporting only a small set of “macro” constraints that are specifically suited to graph drawing. These constraints are enforced by a generalized spring algorithm. The result is a usable and useful tool for drawing small graphs easily and nicely.

Many problems in computer-aided design and graphics involve the process of setting and adjusting input parameters to obtain desirable output values. Exploring different parameter settings can be a difficult and tedious task in most such systems. In the Design GalleryTM (DG) approach, parameter setting is made easier by dividing the task more equitably between user and computer. DG interfaces present the user with the broadest selection, automatically generated and organized, of perceptually different designs that can be produced by varying a given set of input parameters. The DG approach has been applied to several difficult parameter-setting tasks from the field of computer graphics: light selection and placement for image rendering; opacity and color transfer-function specification for volume rendering; and motion control for articulated-figure and particle-system animation. The principal technical challenges posed by the DG approach are dispersion (finding a set of input-parameter vectors that optimally disperses the resulting output values) and arrangement (arranging the resulting designs for easy browsing by the user). We show how effective arrangement can be achieved with 2D and 3D graph drawing. While navigation is easier in the 2D interface, the 3D interface has proven to be surprisingly usable, and the 3D drawings sometimes provide insights that are not so obvious in the 2D drawings.

The glide system is an interactive constraint-based editor for drawing small- and medium-sized graphs (50 nodes or fewer) that organizes the interaction in a more collaborative manner than in previous systems. Its distinguishing features are a vocabulary of specialized constraints for graph drawing, and a simple constraintsatisfaction mechanism that allows the user to manipulate the drawing while the constraints are active. These features result in a graph-drawing editor that is superior in many ways to those based on more general and powerful constraint-satisfaction methods.

We describe a PostScript viewer that provides navigation and annotation functionality similar to that of paper documents using simple unified user-interface techniques.

Can stochastic search algorithms outperform existing deterministic heuristics for the NP-hard problem Number Partitioning if given a sufficient, but practically realizable amount of time? In a thorough empirical investigation using a straightforward implementation of one such algorithm, simulated annealing, Johnson et al. (Ref. 1) concluded tentatively that the answer is negative. In this paper, we show that the answer can be positive if attention is devoted to the issue of problem representation (encoding). We present results from empirical tests of several encodings of Number Partitioning with problem instances consisting of multiple-precision integers drawn from a uniform probability distribution. With these instances and with an appropriate choice of representation, stochastic and deterministic searches can—routinely and in a practical amount of time—find solutions several orders of magnitude better than those constructed by the best heuristic known (Ref. 2), which does not employ searching. We thank David S. Johnson of AT&T Bell Labs for generously and promptly sharing his test instances. For stimulating discussions, we thank members of the Harvard Animation/Optimization Group (especially Jon Christensen), the Computer Science Department at the University of New Mexico, the Santa Fe Institute, and the Berkeley CAD Group. The anonymous referees made numerous constructive suggestions. We thank Rebecca Hayes for comments concerning the figures. The second author is grateful for a Graduate Fellowship from the Fannie and John Hertz Foundation. We thank the Free Software Foundation for making the GNU Multiple Precision package available. The research described in this paper was conducted mostly while the third author was at Digital Equipment Corporation Cambridge Research Lab. This work was supported in part by the National Science Foundation, principally under Grants IRI-9157996 and IRI-9350192 to the fourth author, and by matching grants from Digital Equipment Corporation and Xerox Corporation.

The compact and harmonious layout of ads and text is a fundamental and costly step in the production of commercial telephone directories (ldquoYellow Pagesrdquo). We formulate a canonical version of Yellow-Pages pagination and layout (YPPL) as an optimization problem in which the task is to position ads and text-stream segments on sequential pages so as to minimize total page length and maximize certain layout aesthetics, subject to constraints derived from page-format requirements and positional relations between ads and text. We present a heuristic-search approach to the YPPL problem. Our algorithm has been applied to a sample of real telephone-directory data, and produces solutions that are significantly shorter and better than the published ones.

We present a new heuristic algorithm for graph bisection, based on an implicit notion of clustering. We describe how the heuristic can be combined with stochastic search procedures and a postprocess application of the Kernighan-Lin algorithm. In a series of time-equated comparisons with large-sample runs of pure Kernighan-Lin, the new algorithm demonstrates significant superiority in terms of the best bisections found.

We investigate a family of algorithms for graph bisection that are based on a simple local connectivity heuristic, which we call seed-growth. We show how the heuristic can be combined with stochastic search procedures and a postprocess application of the Kernighan-Lin algorithm. In a series of time-equated comparisons against large-sample runs of pure Kernighan-Lin, the new algorithms find bisections of the same or superior quality. Their performance is particularly good on structured graphs representing important industrial applications. An appendix provides further favorable comparisons to other published results. Our experimental methodology and extensive empirical results provide a solid foundation for further empirical investigation of graph-bisection algorithms.