We present two graph quantities Psi(G,S) and Psi_2(G) which give constant factor estimates to the Dirichlet and Neumann eigenvalues, lambda(G,S) and lambda_2(G), respectively. Our techniques make use of a discrete Hardy-type inequality due to Muckenhoupt.

We present an efficient algorithm for solving a linear system arising from the 1-Laplacian corresponding to a collapsible simplicial complex with a known collapsing sequence. When combined with a result of Chillingworth, our algorithm is applicable to convex simplicial complexes embedded in ℝ3. The running time of our algorithm is nearly-linear in the size of the complex and is logarithmic on its numerical properties. Our algorithm is based on projection operators and combinatorial steps for transferring between them. The former relies on decomposing flows into circulations and potential flows using fast solvers for graph Laplacians, and the latter relates Gaussian elimination to topological properties of simplicial complexes.

We present a new framework for maintaining the quality of two dimensional triangular moving meshes. The use of curved elements is the key idea that allows us to avoid excessive refinement and still obtain good quality meshes consisting of a low number of well shaped elements. We use B-splines curves to model object boundaries, and objects are meshed with second order Bézier triangles. As the mesh evolves according to a non-uniform flow velocity field, we keep track of object boundaries and, if needed, carefully modify the mesh to keep it well shaped by applying a combination of vertex insertion and deletion, edge flipping, and edge smoothing operations at each time step. Our algorithms for these tasks are extensions of known algorithms for meshes built of straight--sided elements and are designed for any fixed-order Bézier elements and B-splines. Although in this work we have concentrated on quadratic elements, most of the operations are valid for elements of any order and they generalize well to higher dimensions. We present results of our scheme for a set of objects mimicking red blood cells subject to a precomputed flow velocity field.

Triangulations of a surface are of fundamental importance in computational geometry, computer graphics, and engineering and scientific simulations. Triangulations are ordinarily represented as mutable graph structures for which both adding and traversing edges take constant time per operation. These representations of triangulations make it difficult to support persistence , including ‘multiple futures’, the ability to use a data structure in several unrelated ways in a given computation; ‘time travel’, the ability to move freely among versions of a data structure; or parallel computation, the ability to operate concurrently on a data structure without interference. We present a purely functional interface and representation of triangulated surfaces, and more generally of simplicial complexes in higher dimensions. In addition to being persistent in the strongest sense, the interface more closely matches the mathematical definition of triangulations (simplicial complexes) than do interfaces based on mutable representations. The representation, however, comes at the cost of requiring O (lg n ) time for traversing or adding triangles (simplices), where n is the number of triangles in the surface. We show both analytically and experimentally that for certain important cases, this extra cost does not seriously affect end-to-end running time. Analytically, we present a new randomized algorithm for 3-dimensional Convex Hull based on our representations for which the running time matches the Ω( n lg n ) lower-bound for the problem. This is achieved by using only O ( n ) traversals of the surface. Experimentally, we present results for both an implementation of the 3-dimensional Convex Hull and for a terrain modeling algorithm, which demonstrate that, although there is some cost to persistence, it seems to be a small constant factor.

Many important phenomena in science and engineering, including our motivating problem of microstructural blood flow, can be modeled as flows with dynamic interfaces. The major challenge faced in simulating such flows is resolving the interfacial motion. Lagrangian methods are ideally suited for such problems, since interfaces are naturally represented and propagated. However, the material description of motion results in dynamic meshes, which become hopelessly distorted unless they are regularly regenerated. Lagrangian methods are particularly challenging on parallel computers, because scalable dynamic mesh methods remain elusive. Here, we present a parallel dynamic mesh Lagrangian method for flows with dynamic interfaces. We take an aggressive approach to dynamic meshing by triangulating the propagating grid points at every timestep using a scalable parallel Delaunay algorithm. Contrary to conventional wisdom, we show that the costs of the geometric components (triangulation, coarsening, refinement, and partitioning) can be made small relative to the flow solver.

A sliver is a tetrahedron whose four vertices lie close to a plane and whose perpendicular projection to that plane is a convex quadrilateral with no short edge. Slivers are both undesirable and ubiquitous in 3-dimensional Delaunay triangulations. Even when the point-set is well-spaced, slivers may result. This paper shows that such a point set permits a small perturbation whose Delaunay triangulation contains no slivers. It also gives deterministic algorithms that compute the perturbation of n points in time O(n log n) with one processor and in time O(log n) with O(n) processors. Keywords. Mesh generation, computational geometry, tetrahedral meshes, Delaunay triangulations, slivers, mesh smoothing, mesh clean-up. 1. INTRODUCTION This paper presents a smoothing and clean-up algorithm for 3-dimensional Delaunay triangulations that removes all slivers. A necessary assumption of the algorithm is that the input triangles and tetrahedra have a bounded circumradius to shortest edge length...

Article A Delaunay based numerical method for three dimensions: generation, formulation, and partition Share on Authors: Gary L. Miller School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania School of Computer Science, Carnegie Mellon University, Pittsburgh, PennsylvaniaView Profile , Dafna Talmor School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania School of Computer Science, Carnegie Mellon University, Pittsburgh, PennsylvaniaView Profile , Shang-Hua Teng Department of Computer Science, University of Minnesota, Minneapolis, Minnesota Department of Computer Science, University of Minnesota, Minneapolis, MinnesotaView Profile , Noel Walkington Department of Mathematics, Carnegie Mellon University, Pittsburgh, Pennsylvania Department of Mathematics, Carnegie Mellon University, Pittsburgh, PennsylvaniaView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 683–692https://doi.org/10.1145/225058.225286Online:29 May 1995Publication History 62citation786DownloadsMetricsTotal Citations62Total Downloads786Last 12 Months7Last 6 weeks0 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 SiteGet Access