Narrow Results

In this paper, we will place clusters in type $\widetilde{𝔸}$ (equivalently triangulations of an annulus) into infinite families parametrized by winding numbers of certain arcs in the corresponding triangulation. We will count how many such families there are and provide an algebraic description of these families in terms of the corresponding cluster category.

Let V be a finite point set in 3-space, and let be the set of triangulated polyhedral surfaces homeomorphic to a sphere and with vertex set V. Let abc and cbd be two adjacent triangles belonging to a surface ; the flip of the edge bc would replace these two triangles by the triangles abd and adc. The flip operation is only considered when it does not produce a self-intersecting surface. In this paper we show that given two surfaces S₁, , it is possible that there is no sequence of flips transforming S₁ into S₂, even in the case that V consists of points in convex position.

The size of a random surface can be measured in at least two ways from two lengths: the radius of gyration and the smallest length such that a box constructed with this length contains the surface. In this paper it is shown that both lengths are non-self-averaging.

A new computational paradigm is described which offers the possibility of superlinear (and sometimes unbounded) speedup, when parallel computation is used. The computations involved are subject only to given mathematical constraints and hence do not depend on external circumstances to achieve superlinear performance. The focus here is on geometric transformations. Given a geometric object A with some property, it is required to transform A into another object B which enjoys the same property. If the transformation requires several steps, each resulting in an intermediate object, then each of these intermediate objects must also obey the same property. We show that in transforming one triangulation of a polygon into another, a parallel algorithm achieves a superlinear speedup. In the case where a convex decomposition of a set of points is to be transformed, the improvement in performance is unbounded, meaning that a parallel algorithm succeeds in solving the problem as posed, while all sequential algorithms fail.

Image related computations are becoming mainstream in today's computing environment. However, Computer Science departments still offer image related courses mostly as electives or at the graduate level. As imaging's importance increases, one needs to consider its coverage at the core courses. Most departments cannot afford to add another course into their curriculum at this level, so the only remaining choice is to integrate image related applications into the existing core courses. This paper addresses this issue as it relates to an Algorithms course. The specific prerequisites and goals of our Algorithms course are described. The image related applications that have been adopted are presented and their impact on the course is discussed.

Research on software measurement can be organized around five key conceptual and methodological issues: how to apply measurement theory to software, how to frame software metrics, how to develop metrics, how to collect core measures, and how to analyze measures. The subject is of special concern for the industry, which is interested in improving practices — mainly in developing countries, where the software industry represents an opportunity for growth and usually receives institutional support for matching international quality standards. Academics are also in need of understanding and developing more effective methods for managing the software process and assessing the success of products and services, as a result of an enhanced awareness about the emergency of aligning business processes and information systems. This paper unveils the fundamentals of measurement in software engineering and discusses current issues and foreseeable trends for the subject. A literature review was performed within major academic publications in the last decade, and findings suggest a sensible shift of measurement interests towards managing the software process as a whole — without losing from sight the customary focus on hard issues like algorithm efficiency and worker productivity.

We propose algorithms to enumerate (1) regular triangulations, (2) spanning regular triangulations, (3) equivalence classes of regular triangulations with respect to symmetry, and (4) all triangulations. All of the algorithms are for arbitrary points in general dimension. They work in output-size sensitive time with memory only of several times the size of a triangulation. For the enumeration of regular triangulations, we use the fact by Gel'fand, Zelevinskii and Kapranov that regular triangulations correspond to the vertices of the secondary polytope. We use reverse search technique by Avis and Fukuda, its extension for enumerating equivalence classes of objects, and a reformulation of a maximal independent set enumeration algorithm. The last approach can be extended for enumeration of dissections.

Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T) using constrained Delaunay triangulation. We show that this minimal set is precisely the set of non locally Delaunay edges, and that its cardinality is less than or equal to n+i/2 (if i is the number of interior points in T), which is a tight bound.

We introduce a new algorithm to convert triangular meshes of polygonal regions, with or without holes, into strictly convex quadrilateral meshes of small bounded size. Our algorithm includes all vertices of the triangular mesh in the quadrilateral mesh, but may add extra vertices (called Steiner points). We show that if the input triangular mesh has t triangles, our algorithm produces a mesh with at most quadrilaterals by adding at most t+2 Steiner points, one of which may be placed outside the triangular mesh domain. We also describe an extension of our algorithm to convert constrained triangular meshes into constrained quadrilateral ones. We show that if the input constrained triangular mesh has t triangles and its dual graph has h connected components, the resulting constrained quadrilateral mesh has at most quadrilaterals and at most t+3h Steiner points, one of which may be placed outside the triangular mesh domain. Examples of meshes generated by our algorithm, and an evaluation of the quality of these meshes with respect to a quadrilateral shape quality criterion are presented as well.

Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle.

In this paper we consider a natural extension of this problem: Given in addition a Steiner pointp, determine the optimal location of p and a triangulation of X ∪ {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial-time algorithm for this problem and then extend our solution to handle any constant number of Steiner points.

Several Representations and Coding schemes have been proposed to represent efficiently 2D triangulations. In this paper, we propose a new practical approach to reduce the main memory space needed to represent an arbitrary triangulation, while maintaining constant time for some basic queries. This work focuses on the connectivity information of the triangulation, rather than the geometric information (vertex coordinates), since the combinatorial data represents the main part of the storage. The main idea is to gather triangles into patches, to reduce the number of pointers by eliminating the internal pointers in the patches and reducing the multiple references to vertices. To accomplish this, we define and use stable catalogs of patches that are closed under basic standard update operations such as insertion and deletion of vertices, and edge flips. We present some bounds and results concerning special catalogs, and some experimental results that exhibit the practical gain of such methods.

We describe an algorithm to triangulate a general map on an arbitrary surface in such way that the resulting triangulation is vertex-colorable with three colors. (Three-colorable triangulations can be efficiently represented and manipulated by the GEM data structure of Montagner and Stolfi.) The standard solution to this problem is the barycentric subdivision, which produces $4e-2b$ triangles when applied to a map with $e$ edges, such that $b$ of them are border edges (adjacent to only one face). Our algorithm yields a subdivision with at most $2e-b+2(2-\chi )$ triangles, where $\chi$ is the Euler Characteristic of the surface; or at most $2e-b+2(2-\chi )-n+(2(2-\chi )-b)/(D-2)$ triangles if all $n$ faces of the map have the same degree $D$. Experimental results show that the resulting triangulations have, on the average, significantly fewer triangles than these upper bounds.

We study the shortest $k$-violation path problem in a simple polygon. Let $P$ be a simple polygon in ${ℝ}^2$ with $n$ vertices and let $s,t$ be a pair of points in $P$. Let $int(P)$ represent the interior of $P$. Let $\tilde{P}={ℝ}^2\backslash int(P)$ represent the exterior of $P$. For an integer $k\ge 0$, the shortest $k$-violation path problem in $P$ is the problem of computing the shortest path from $s$ to $t$ in $P$, such that at most $k$ path segments are allowed to be in $\tilde{P}$. The subpaths of a $k$-violation path are not allowed to bend in $\tilde{P}$. For any $k$, we present a $(1+2𝜖)$ factor approximation algorithm for the problem that runs in $O(n^2{\sigma }^{2}klog{n}^2{\sigma }^2+n^2{\sigma }^{2}k)$ time. Here $\sigma =O({log}_{\delta }(\frac{L}{r}))$ and $\delta$, $L$, $r$ are geometric parameters.

We describe randomized parallel algorithms for building trapezoidal diagrams of line segments in the plane. The algorithms are designed for a CRCW PRAM. For general segments, we give an algorithm requiring optimal O(A+n log n) expected work and optimal O(log n) time, where A is the number of intersecting pairs of segments. If the segments form a simple chain, we give an algorithm requiring optimal O(n) expected work and O(log n log log n log* n) expected time, and a simpler algorithm requiring O(n log* n) expected work. The serial algorithm corresponding to the latter is among the simplest known algorithms requiring O(n log* n) expected operations. For a set of segments forming K chains, we give an algorithm requiring O(A+n log* n+K log n) expected work and O(log n log log n log* n) expected time. The parallel time bounds require the assumption that enough processors are available, with processor allocations every log n steps.

We describe methods for triangulating polygonal regions of the plane so that no triangle has a large angle. Our main result is that a polygon with n sides can be triangulated with O(n²) nonobtuse triangles. We also show that any triangulation (without Steiner points) of a simple polygon has a refinement with O(n⁴) nonobtuse triangles. Finally we show that a triangulation whose dual is a path has a refinement with only O(n²) nonobtuse triangles.

Maximal balls (and the associated maximal spheres) between sets arise naturally in several areas of computational geometry such as the Voronoi diagram and the symmetric axis transform. We give necessary and sufficient conditions for the existence and uniqueness of maximal spheres to pass through specified points in a linear separator between sets in E^d. These results are applicable in certain problems of simplicial decomposition of domains.

Three open problems on tetrahedralizations are described: Does bisection refinement keep solid angles bound away from zero? Can a tetrahedralization be frozen with respect to flips? Do points in convex position have a Hamiltonian tetrahdralization?

Recent advances on polygon triangulation have yielded efficient algorithms for a large number of problems dealing with a single simple polygon. If the input consists of several disjoint polygons, however, it is often desirable to merge them in preprocessing so as to produce a single polygon that retains the geometric characteristics of its individual components. We give an efficient method for doing so, which combines a generalized form of Jordan sorting with the efficient use of point location and interval trees. As a corollary, we are able to triangulate a collection of p disjoint Jordan polygonal chains in time O (n + p (log p)^1+ε), for any fixed ε > 0, where n is the total number of vertices. A variant of the algorithm gives a running time of O ((n + p log p) log log p). The performance of these solutions approaches the lower bound of Ω (n + p log p).

We show how to triangulate polygonal regions—adding extra vertices as necessary— with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle in a triangulation of an n-vertex polygon (with holes) is a constant fraction of the largest possible. Using O(n log n) triangles for simple polygons or O(n^3/2) triangles for polygons with holes, we can guarantee that the largest angle is no greater than 150°. We can add the guarantee on smallest height to these no-large-angle results, without increasing the asymptotic complexity of the triangulation. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n^1.85) triangles.

We study the problem of covering a simple orthogonal polygon with a minimum number of (possibly overlapping) squares, all internal to the polygon. The problem has applications in VLSI mask generation, incremental update of raster displays, and image compression. We give a linear time algorithm for covering a simple polygon, specified by its vertices, with squares. Covering with similar rectangles (having a given x/y ratio) is an equivalent problem.