Recent studies of irregular applications such as finite-element mesh generators and data-clustering codes have shown that these applications have a generalized data parallelism arising from the use of iterative algorithms that perform computations on elements of worklists. In some irregular applications, the computations on different elements are independent. In other applications, there may be complex patterns of dependences between these computations.

Recent application studies have shown that many irregular applications have a generalized data parallelism that manifests itself as iterative computations over worklists of different kinds. In general, there are complex dependencies between iterations. These dependencies cannot be elucidated statically because they depend on the inputs to the program; thus, optimistic parallel execution is the only tractable approach to parallelizing these applications.

Irregular applications, which manipulate large, pointer-based data structures like graphs, are difficult to parallelize manually. Automatic tools and techniques such as restructuring compilers and run-time speculative execution have failed to uncover much parallelism in these applications, in spite of a lot of effort by the research community. These difficulties have even led some researchers to wonder if there is any coarse-grain parallelism worth exploiting in irregular applications.

A protein can be considered as a string (on the alphabet of 20 amino acids) or as a structure (each protein folds into a particular 3D configuration). Consider the following string-based problem: Given two protein strings that are not necessarily similar in their entirety, determine the most similar contiguous substrings, one from each protein. The exact meaning of most similar here is determined by the user; it is based on user-specified scores for character vs. character similarity and for character vs. space similarity. It is important to allow for spaces or gaps because evolutionary changes to proteins often involve insertion or deletion of one or more individual amino acids. For this kind of string-based similarity, the most-similar substrings can be determined in time O(mn) using Dynamic Programming (DP).The goal here is to design an algorithm for similarity of protein structures as opposed to protein strings. The inspiration for our algorithm is drawn from the DP-based similarity algorithm for strings. Instead of comparing sequences of characters, we compare sequences of vectors. One complication for working with structures instead of strings is the problem of orientation: basically, two structures that have similar shape can "look different" if they are at different orientations. Algorithmically, this means that we must establish the optimal orientations for our two proteins as well as finding the similar subsequences. In other words, an algorithm for similarity of structures involves both discrete optimization (to find the corresponding subsequences) and continuous optimization (to find the optimal orientation). Interestingly, if the correspondence is given then the optimal orientation (for that correspondence) is easy to find, and if the the orientation is given then the optimal correspondence (for that orientation) is easy to find. The challenge is to accomplish both optimizations at once. Note that the technique presented here produces a globally optimal solution; there are no approximations or assumptions of randomness.

We define and prove properties of the consensus shape for a family of proteins, a protein-like structure that provides a compact summary of the significant structural information for a protein family. If all members of a protein family exhibit a geometric relationship between corresponding alpha carbons then that relationship is preserved in the consensus shape. In particular, distances and angles that are consistent across family members are preserved. For the consensus shape, the spacing between successive alpha carbons is variable, with small distances in regions where the members of the protein family exhibit significant variation and large distances (up to the standard spacing of about 4\AA) in regions where the family members agree. Despite this non-protein-like characteristic, the consensus shape preserves and highlights important structural information. We describe an iterative algorithm for computing the consensus shape and prove that the algorithm converges. We also present the results of experiments in which we build consensus shapes for several known protein families.

We describe a distributed memory parallel Delaunay refinement algorithm for polyhedral domains which can generate meshes containing tetrahedra with circumradius to shortest edge ratio less than 2, as long as the angle separating any two incident segments and/or facets is between 90° and 270° degrees. Input to our implementation is an element--wise partitioned, conforming Delaunay mesh of a restricted polyhedral domain which has been distributed to the processors of a parallel system. The submeshes of the distributed mesh are then independently refined by concurrently inserting new mesh vertices.Our algorithm allows a new mesh vertex to affect both the submesh tetrahedralizations and the submesh interfaces induced by the partitioning. This flexibility is crucial to ensure mesh quality, but it introduces unpredictable and variable latencies due to long delays in gathering remote data required for updating mesh data structures. In our experiments, more than 80% of this latency was masked with computation due to the fine--grained concurrency of our algorithm.Our experiments also show that the algorithm is efficient in practice, even for certain domains whose boundaries do not conform to the theoretical limits imposed by the algorithm. The algorithm we describe is the first step in the development of much more sophisticated guaranteed--quality parallel mesh generation algorithms.

We consider the problem of identifying common threedimensional substructures between proteins.Our method is based on comparing the shape of the a-carbon backbone structures of the proteins in order to find 3D rigid motions that bring portions of the geometric structures into correspondence.We propose a geometric representation of protein backbone chains that is compact yet allows for similarity measures that are robust against noise and outliers.We represent the structure of the backbone as a sequence of unit vectors, defined by each adjacent pair of a-carbons; we then define a measure of the similarity of two protein structures baaed on the RMS (root mean squared) distance between corresponding orientation vectors of the two proteins.Our measure has several advantages over measures that are commonly used for comparing protein shapes, such as the minimum RMS distance between the 3D positions of corresponding atoms in two proteins.This

We consider the following geometric pattern matching problem: find the minimum Hausdorff distance between two point sets under translation with L1 or L∞ as the underlying metric. Huttenlocher, Kedem and Sharir have shown that this minimum distance can be found by constructing the upper envelope of certain Voronoi surfaces. Further, they show that if the two sets are each of cardinality n then the complexity of the upper envelope of such surfaces is Ω(n3). We examine the question of whether one can get around this cubic lower bound, and show that under the L1 and L∞ metrics, the time to compute the minimum Hausdorff distance between two point sets is O(n2log2n).

Article Free Access Share on Guaranteed-quality Delaunay meshing in 3D (short version) Author: L. Paul Chew Department of Computer Science, Cornell University, Ithaca, NY Department of Computer Science, Cornell University, Ithaca, NYView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 391–393https://doi.org/10.1145/262839.263018Online:01 August 1997Publication History 68citation785DownloadsMetricsTotal Citations68Total Downloads785Last 12 Months20Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Given a set of n moving points in the plane, how many topological changes occur in the Voronoi diagram of the points? If each point has constant velocity then there is an upper bound of O(n3) (Guibas et al., 1991) and an easy lower bound of Ω(n2). It is widely believed that the true upper bound should be close to O(n2). We show this belief to be true for the case of Voronoi diagrams based on the L1 (or L∞) metric; the number of changes is shown to be O(n2α(n)) where α(n) grows so slowly it is effectively a small constant for all reasonable values of n.

Given two planar sets A and B, we examine the problem of determining the smallest ϵ such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within distance ϵ of some member of B. We establish upper bounds on the combinatorial complexity of this subproblem in model-based computer vision, when the sets A and B contain points, line segments, or (filled-in) polygons. We also show how to use our methods to substantially improve on existing algorithms for finding the minimum Hausdorff distance under Euclidean motion.

For several commonly-used solution techniques for partial differential equations, the first step is to divide the problem region into simply-shaped elements, creating a mesh. We present a technique for creating high-quality triangular meshes for regions on curved surfaces. This technique is an extension of previous methods we developed for regions in the plane. For both flat and curved surfaces, the resulting meshes are guaranteed to exhibit the following properties: (1) internal and external boundaries are respected, (2) element shapes are guaranteed—all elements are triangles with angles between 30 and 120 degrees (with the exception of badly shaped elements that may be required by the specified boundary), and (3) element density can be controlled, producing small elements in “interesting” areas and large elements elsewhere. An additional contribution of this paper is the development of a practical generalization of Delaunay triangulation to curved surfaces.

A method for comparing polygons that is a metric, invariant under translation, rotation, and change of scale, reasonably easy to compute, and intuitive is presented. The method is based on the L/sub 2/ distance between the turning functions of the two polygons. It works for both convex and nonconvex polygons and runs in time O(mn log mn), where m is the number of vertices in one polygon and n is the number of vertices in the other. Some examples showing that the method produces answers that are intuitively reasonable are presented.>

Given a convex polygon P and an environment consisting of polygonal obstacles, we find the largest similar copy of P that does not intersect any of the obstacles. Allowing translation, rotation, and change-of-size, our method combines a new notion of Delaunay triangulation for points and edges with the well-known functions based on Davenport-Schinzel sequences producing an almost quadratic algorithm for the problem. Namely, if P is a convex k-gon and if Q has n corners and edges then we can find the placement of the largest similar copy of P in the environment Q in time Ο(k4n λ4(kn) log n), where λ4 is one of the almost-linear functions related to Davenport-Schinzel sequences. If the environment consists only of points then we can find the placement of the largest similar copy of P in time Ο(k2n λ3(kn) log n).

Given a set of n vertices in the plane together with a set of noncrossing edges, the constrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimal Ο(n log n) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (nonDelaunay) triangulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that should make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles in the plane and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.

Given a robot R, a set S of obstacles, and points p and q, the Shortest Path Problem is to find the shortest path for R to move from p to q without crashing into any of the obstacles. We show that if the problem is restricted to a disc-shaped robot in the plane with nonintersecting polygons as obstacles then the shortest path can be found in time O(n2log n) where n is the number of edges that make up the polygonal obstacles. This matches the best time currently known for the simpler problem of finding the shortest path in the plane for a point robot.

We present an “expanding waves” view of Voronoi diagrams that allows such diagrams to be defined for very general metrics and for distance measures that do not qualify as metrics. If a pebble is dropped into a still pond, circular waves move out from the point of impact. If n pebbles are dropped simultaneously, the places where wave fronts meet define the Voronoi diagram on the n points of impact.