International Journal of Computational Geometry & Applications

We perform a probabilistic study of discrete attributes of moving points. In our probabilistic model, an item is given an initial position and a velocity drawn independently at random from the same distribution. We study the expected number of changes that happen to the closest pair, the Voronoi diagram, and the convex hull of a set of such moving items.

The automatic placement of text or symbol labels corresponding to graphical features is critical in several application areas such as cartography, geographical information systems, and graph drawing. In this paper we present a general framework for solving the problem of assigning text or symbol labels to a set of graphical features in two dimensional drawings or maps. Our approach does not favor the labeling of one type of graphical feature (such as a node, edge, or area) over another. Additionally, the labels are allowed to have arbitrary size and orientation. We also present a fast and simple technique, based on the general framework, for assigning labels to edges of graph drawings. We have implemented our techniques and have performed extensive experimentation on hierarchical and orthogonal drawings of graphs. The resulting label assignments are very practical and indicate the effectiveness of our approach.

We present the use of mapping functions to automatically generate levels of detail with known error bounds for polygonal models. We develop a piece-wise linear mapping function for each simplification operation and use this function to measure deviation of the new surface from both the previous level of detail and from the original surface. In addition, we use the mapping function to compute appropriate texture coordinates if the original model has texture coordinates at its vertices. Our overall algorithm uses edge collapse operations. We present rigorous procedures for the generation of local orthogonal projections to the plane as well as for the selection of a new vertex position resulting from the edge collapse operation. The algorithm computes guaranteed error bounds on surface deviation and produces an entire continuum of levels of detail with mappings between them. We demonstrate the effectiveness of our algorithm on several models: a Ford Bronco consisting of over 300 parts and 70, 000 triangles, a textured lion model consisting of 49 parts and 86, 000 triangles, a textured, wrinkled torus consisting of 79, 000 triangles, a dragon model consisting of 871, 000 triangles, a Buddha model consisting of 1,000,000 triangles, and an armadillo model consisting of 2, 000, 000 triangles.