Abstract We consider a cross field, possibly with singular points of valence 3 or 5, in which all streamlines are finite, and either end on the boundary or form cycles. We show that we can always assign lengths to the two cross field directions to produce an anisotropic orthogonal frame field. There is a one‐dimensional family of such length functions, and we optimize within this family so that the two lengths are everywhere as similar as possible. This gives a numerical bound on the minimal anisotropy of any quad mesh exactly following the input cross field. We also show how to remove some limit cycles.

We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU.

We design a family of parallel algorithms and GPU implementations for the exact string matching problem, based on Rabin-Karp (RK) randomized string matching. We describe and analyze three primary parallel approaches to binary string matching: cooperative (CRK), divide-and-conquer (DRK), and a novel hybrid of both (HRK). The CRK is most effective for large patterns (>8K characters), while the DRK approach is superior for shorter patterns. We then generalize the DRK to support any alphabet size without loss of performance. Our DRK method achieves up to a 64 GB/s processing rate on 8-character patterns from an 8-bit alphabet on an NVIDIA Tesla K40c GPU. We next demonstrate a novel parallel two-stage matching method (DRK-2S), which first skims the text for a smaller subset of the pattern and then verifies all potential matches in parallel. Our DRK-2S method is superior for pattern sizes up to 64k compared to the fastest CPU-based string matching implementations. With an 8-bit alphabet and up to 1k-character patterns, we get a geometric mean speedup of 4.81x against the best CPU methods, and can achieve a processing rate of at least 53 GB/s.

Abstract Given a shape, a skeleton is a thin centered structure which jointly describes the topology and the geometry of the shape. Skeletons provide an alternative to classical boundary or volumetric representations, which is especially effective for applications where one needs to reason about, and manipulate, the structure of a shape. These skeleton properties make them powerful tools for many types of shape analysis and processing tasks. For a given shape, several skeleton types can be defined, each having its own properties, advantages, and drawbacks. Similarly, a large number of methods exist to compute a given skeleton type, each having its own requirements, advantages, and limitations. While using skeletons for two‐dimensional (2D) shapes is a relatively well covered area, developments in the skeletonization of three‐dimensional (3D) shapes make these tasks challenging for both researchers and practitioners. This survey presents an overview of 3D shape skeletonization. We start by presenting the definition and properties of various types of 3D skeletons. We propose a taxonomy of 3D skeletons which allows us to further analyze and compare them with respect to their properties. We next overview methods and techniques used to compute all described 3D skeleton types, and discuss their assumptions, advantages, and limitations. Finally, we describe several applications of 3D skeletons, which illustrate their added value for different shape analysis and processing tasks.

Recent 3D sketch tools produce networks of three-space curves that suggest the contours of shapes. The shapes may be non-manifold, closed three-dimensional, open two-dimensional, or mixed. Our video demonstrates a system that automatically generates intuitively appealing, piecewise-smooth surface patches from such a curve network, and an intelligent user interface for modifying the automatically chosen surface patches. Both parts of the system use a linear algebra representation of the set of surface patches to track the topology.

Abstract Recent 3D sketch tools produce networks of three‐space curves that suggest the contours of shapes. The shapes may be non‐manifold, closed three‐dimensional, open two‐dimensional, or mixed. We describe a system that automatically generates intuitively appealing piecewise‐smooth surfaces from such a curve network, and an intelligent user interface for modifying the automatically chosen surface patches. Both the automatic and the semi‐automatic parts of the system use a linear algebra representation of the set of surface patches to track the topology. On complicated inputs from ILoveSketch [ BBS08 ], our system allows the user to build the desired surface with just a few mouse‐clicks.

BACKGROUND: The problem of determining the physical conformation of a protein dimer, given the structures of the two interacting proteins in their unbound state, is a difficult one. The location of the docking interface is determined largely by geometric complementarity, but finding complementary geometry is complicated by the flexibility of the backbone and side-chains of both proteins. We seek to generate candidates for docking that approximate the bound state well, even in cases where there is backbone and/or side-chain difference from unbound to bound states. RESULTS: We divide the surfaces of each protein into local patches and describe the effect of side-chain flexibility on each patch by sampling the space of conformations of its side-chains. Likely positions of individual side-chains are given by a rotamer library; this library is used to derive a sample of possible mutual conformations within the patch. We enforce broad coverage of torsion space. We control the size of the sample by using energy criteria to eliminate unlikely configurations, and by clustering similar configurations, resulting in 50 candidates for a patch, a manageable number for docking. CONCLUSIONS: Using a database of protein dimers for which the bound and unbound structures of the monomers are known, we show that from the unbound patch we are able to generate candidates for docking that approximate the bound structure. In patches where backbone change is small (within 1 Å RMSD of bound), we are able to account for flexibility and generate candidates that are good approximations of the bound state (82% are within 1 Å and 98% are within 1.4 Å RMSD of the bound conformation). We also find that even in cases of moderate backbone flexibility our candidates are able to capture some of the overall shape change. Overall, in 650 of 700 test patches we produce a candidate that is either within 1 Å RMSD of the bound conformation or is closer to the bound state than the unbound is.

Abstract We present a closed‐form solution for the symmetrization problem, solving for the optimal deformation that reconciles a set of local bilateral symmetries. Given as input a set of point‐pairs which should be symmetric, we first compute for each local neighborhood a transformation which would produce an approximate bilateral symmetry. We then solve for a single global symmetry which includes all of these local symmetries, while minimizing the deformation within each local neighborhood. Our main motivation is the symmetrization of digitized fossils, which are often deformed by a combination of compression and bending. In addition, we use the technique to symmetrize articulated models.

Abstract Optical triangulation laser scanners produce errors at surface discontinuities and sharp features. These systematic errors are anisotropic. We examine the causes of these errors theoretically, and we study the correlation of systematic error with edge size and orientation experimentally. We then present a novel processing method for removing systematic errors, by combining scans taken at several different orientations. We apply an anisotropic filter to the separate scans, and use it to weight the data in a final combination step. Unlike previous approaches, our method does not require access to the scanner's internal data or firmware. We demonstrate the technique on data from laser range scanners by two different manufacturers.

Localized Components Analysis (LoCA) is a new method for describing surface shape variation in an ensemble of objects using a linear subspace of spatially localized shape components. In contrast to earlier methods, LoCA optimizes explicitly for localized components and allows a flexible trade-off between localized and concise representations, and the formulation of locality is flexible enough to incorporate properties such as symmetry. This paper demonstrates that LoCA can provide intuitive presentations of shape differences associated with sex, disease state, and species in a broad range of biomedical specimens, including human brain regions and monkey crania.

We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself, and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching.

We introduce a volumetric space-time technique for the reconstruction of moving and deforming objects from point data. The output of our method is a four-dimensional space-time solid, made up of spatial slices, each of which is a three-dimensional solid bounded by a watertight manifold. The motion of the object is described as an incompressible flow of material through time. We optimize the flow so that the distance material moves from one time frame to the next is bounded, the density of material remains constant, and the object remains compact. This formulation overcomes deficiencies in the acquired data, such as persistent occlusions, errors, and missing frames. We demonstrate the performance of our flow-based technique by reconstructing coherent sequences of watertight models from incomplete scanner data.

UNLABELLED: We describe a general multiplatform exploratory tool called TreeQ-Vista, designed for presenting functional annotations in a phylogenetic context. Traits, such as phenotypic and genomic properties, are interactively queried from a user-provided relational database with a user-friendly interface which provides a set of tools for users with or without SQL knowledge. The query results are projected onto a phylogenetic tree and can be displayed in multiple color groups. A rich set of browsing, grouping and query tools are provided to facilitate trait exploration, comparison and analysis. AVAILABILITY: The program, detailed tutorial and examples are available online (http:/genome.lbl.gov/vista/TreeQVista).

The MLS surface [Levin 2003], used for modeling and rendering with point clouds, was originally defined algorithmically as the output of a particular meshless construction. We give a new explicit definition in terms of the critical points of an energy function on lines determined by a vector field. This definition reveals connections to research in computer vision and computational topology.Variants of the MLS surface can be created by varying the vector field and the energy function. As an example, we define a similar surface determined by a cloud of surfels (points equipped with normals), rather than points.We also observe that some procedures described in the literature to take points in space onto the MLS surface fail to do so, and we describe a simple iterative procedure which does.

Randomized incremental constructions are widely used in computational geometry, but they perform very badly on large data because of their inherently random memory access patterns. We define a biased randomized insertion order which removes enough randomness to significantly improve performance, but leaves enough randomness so that the algorithms remain theoretically optimal.

The problem of computing a piecewise linear approximation to a surface from a set of sample points is important in solid modeling, computer graphics and computer vision. A recent algorithm [1] using the Voronoi diagram of the sample points gave a guarantee on the distance of the output surface from the original sampled surface assuming the sample was `suciently dense'. We give a similar algorithm, simplifying the computation and the proof of the geometric guarantee. In addition, we guarantee that our output surface is homeomorphic to the original surface; to our knowledge this is the rst such topological guarantee for this problem. 1 Introduction A number of applications in CAD, computer graphics, computer vision and mathematical modeling involve the computation of a piecewise lin- Dept. of Computer Science, U. of Texas, Austin TX 78712. e-mail: [email protected], supported by NSF grant CCR-9731977 y Dept. of Computer Science, U. of Texas, Austin, TX 78712. e-mail: sunghe...

Given a sample of points from the boundary of an object IR3, we construct a representation of the object as a union of balls. We use many fewer balls than previous constructions, but our shape representation is better. We bound the distance from the surface of the union to the original object surface, and show that when the sampling is sufficiently dense the two are homeomorphic. This implies a topolgical relationship between the true medial axis of the object and both the medial axis, and the α-shape, of the union of balls. We show that the set of ball centers in our construction converges to the true medial axis as the sampling density increases.

No abstract available.

We give a simple combinatorial algorithm that computes a piecewlze-linear approximation of a smooth surface from a finite set of sample points.The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation.We prove the algorithm correct by showing that for densely sampled surfaces, where density depends on "local feature size", the output is topologically valid and convergent (both point&e and in surface normals) to the original surface.We deocribe an implementation of the algorithm and shorr example outputs.

We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR 3 .The al- gorithm is the first for this problem with provable guarantees.Given a "good sample" from a smooth surface, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling density increases.The definition of a good sample is itself interesting: the required sampling density varies locally, rigorously capturing the intuitive notion that featureless areas can be reconstructed from fewer samples.The output mesh interpolates, rather than approximates, the input points.Our algorithm is based on the three-dimensional Voronoi diagram.Given a good program for this fundamental subroutine, the algorithm is quite easy to implement.

No abstract available.

W'e give a lower bound of 0( ~ldt2j ) for the number of vertices of ad-dimensional polytope with ffacetswllich canappear on the outer boundary of a projection to dimension 2 < k < d.By duality, this implies a lower bound of Q( n ld\2j ) for the number of facets in a k-dimensional slice of a d-dimensional polytope with n vertices. .

No abstract available.

In the first part of this paper, we reduce two geometric optimization problems to convex programming: finding the largest axis-aligned box in the intersection of a family of convex sets, and finding the translation and scaling that minimizes the Hausdorff distance between two polytopes. These reductions imply that important cases of these problems can be solved in expected linear time. In the second part of the paper, we use convex programming to give a new, short proof of an interesting Helly-type theorem, first conjectured by Gru¨nbaum and Motzkin.

Recent combinatorial algorithms for linear programming also solve certain non-linear problems. We call these Generalized Linear Programming, or GLP, problems. One way in which convexity has been generalized by mathematicians is through a collection of results called the Helly theorems. We show that the every GLP problem implies a Helly theorem, and we give two paradigms for constructing a GLP problem from a Helly theorem. We give many applications, including linear expected time algorithms for finding line transversals and hyperplane fitting in convex metrics. These include GLP problems with the surprising property that the constraints are non-convex or even disconnected. We show that some Helly theorems cannot be turned into GLP problems.