38065257
Tetrahedralization of Two Nested Convex Polyhedra
In this paper, we present an algorithm to tetrahedralize the region between two nested convex polyhedra without introducing Steiner points. The resulting tetrahedralization consists of linear number of tetrahedra. Thus, we answer the open problem raised by Chazelle and Shouraboura: "whether or not one can tetrahedralize the region between two nested convex polyhedra into linear number of tetrahedra, avoiding Steiner points?". Our algorithm runs in O((n+m)3 log(n+m)) time and produces 2(m+n-3) tetrahedra, where n and m are the numbers of the vertices in the two given polyhedra, respectively.
46528104
Optimal Tetrahedralizations of Some Convex Polyhedra
35234330
A Parallel Algorithm for Finding the Constrained Voronoi Diagram of Line Segments in the Plane
In this paper, we present an O(1/αlog n) (for any constant 0 ≤ α ≤ 1) time parallel algorithm for constructing the constrained Voronoi diagram of a set L of n non-crossing line segments in E2, using O(n1+α) processors on a CREW PRAM model. This parallel algorithm also constructs the constrained Delaunay triangulation of L in the same time and processor bound by the duality. 
 
Our method established the conversions from finding the constrained Voronoi diagram L to finding the Voronoi diagram of S, the endpoint set of L. We further showed that this conversion can be done in O(log n) time using n processors in CREW PRAM model. The complexity of the conversion implies that any improvement of the complexity for finding the Voronoi diagram of a point set will automatically bring the improvement of the one in question.
40171838
Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes
A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes.
18478446
On Parallel Complexity of Planar Triangulations
The greedy triangulation of a finite planar point set is obtained by repeatedly inserting a shortest diagonal that doesn't intersect those already in the plane. We show that the problem of constructing the greedy triangulation of a finite set of points with integer coordinates in the plane is P-complete. This is the first known geometric P-complete problem where the input is given as a set of points. On the other hand, we provide general NC-methods for testing whether a given triangulation of a set of points and/or line segments can be built by inserting the diagonals in a given partial order, and for constructing such triangulations for simple polygons. As corollaries, we obtain NC-algorithms for testing whether a triangulation is respectively the greedy triangulation or the so called sweep-line triangulation, and for constructing respectively the greedy triangulation or the sweep-line triangulation of a simple polygon. The latter result solves the open problem posed by Atallah et al.
5531222
Divide and Compose: SCC Refinement for Language Emptiness
We propose a refinement approach to symbolic SCC analysis, which performs large parts of the computation on abstracted systems, and on small subsets of the state space. For language-emptiness checking, it quickly discards uninteresting parts of the state space; for the remaining states, it adapts the model checking computation to the strength of the SCCs at hand. 
 
We present a general framework for SCC refinement, which uses a compositional approach to generate and refine overapproximations. We show that our algorithm significantly outperforms the one of Emerson and Lei.
7862760
Tagged Probe Interval Graphs
A generalization of interval graph is introduced for cosmid contig mapping of DNA. A graph is a tagged probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and one end of its corresponding interval is contained in the interval corresponding to the other vertex. We show that tagged probe interval graphs are weakly triangulated graphs, hence are perfect graphs. For a tagged probe interval graph with a given partition, we give a chordal completion that is consistent to any interval completions with respect to the same vertex partition.
37036367
A New Routing Algorithm for Cyclic Shifts on BRGC Hypercubes
The hypercube is one of the most efficient networks for parallel computation. It can efficiently simulate any other network of the same size. In particular, the N-node hypercube can simulate any O(N)-node array, binary tree, or mesh of trees with only a small constant factor slowdown [3]. Furthermore, it is completely symmetric and decomposable into sub-hypercubes. These properties, in addition to its simplicity, make it be an excellent and popular architecture for distributed memory parallel computers. Arrays are natural (data or process) structures for many applications. They can be embedded onto hypercube nodes either in natural order or in Binary-Reflected Gray Code (BRGC) order. It has been noted [2] that many algorithms use the cyclic shift (or rotation) in a natural way as a primitive step. Hence, efficient implementation of cyclic shifts on hypercube network is vita1 to the performance of hypercube computers. Cyclic shift algorithms for the natural order embedding have been studied in [51 and those for the BRGC embedding have been studied in [2,4]. The BRGC embedding has the property that any two adjacent numbers are mapped to neighboring nodes that can communicate directly through a link. Therefore, it uses only one link to route a message from any node to its sink node when the shift distance is one. In this case, it is superior to the natural order embedding. The existing cyclic shift algorithms for the BRGC embedding usually route a message by correcting successive bits that differ in source and sink nodes from the less significant end to the more significant end or in the other order with some exceptions. However, all the algorithms have their drawbacks. For example, the two algorithms presented by Johnsson [2] are neither link-disjoint. Thus, two routing paths will contend for the same link. This not only implies the need for local buffering to route the conflicting messages but also leads to the slowdown of the performance. The best disjoint link algorithm in the literature is the one proposed by Ouyang and Palem [4], which in the worst case uses $fi links to route a message from any node to its cyclic shifted sink node on an n-dimensional BRGC hypercube. There also have been many researches on the problem of general permutation routing [ll, but their algorithms are all asymptotically efficient and are not suitable for the cyclic shift problem. In this paper, we propose a new routing algorithm for cyclic shifts on BRGC hypercubes based on the divide-and-conquer approach instead of the usual one. It uses at most IZ links to route a message from any node to its cyclic shifted sink node on an n-dimensional BRGC hypercube and
14588645
Community Tools for Repurposing Learning Objects
A critical success factor for the reuse of learning objects is the ease by which they may be repurposed in order to enable reusability in a different teaching context from which they were originally designed. The current generation of tools for creating, storing, describing and locating learning objects are best suited for users with technical expertise. Such tools are an obstacle to teachers who might wish to perform alterations to learning objects in order to make them suitable for their context. In this paper we describe a simple set of tools to enable practitioners to adapt the content of existing learning objects and to store and modify metadata describing the intended teaching context of these learning objects. We are deploying and evaluating these tools within the UK language teaching community.
22896034
Compiler Techniques for Extracting Loop-Level Parallelism