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...

In this paper we are concerned with developing a practical parallel algorithm for Delaunay triangulation that works well on general distributions, particularly those that arise in Scientific Computation. Although there have been many theoretical algorithms for the problem, and some implementations based on bucketing that work well for uniform distributions, there has been little work on implementations for general distributions. We use the well known reduction of 2D Delaunay triangulation to 3D convex hull of points on a sphere or paraboloid. A variant of the Edelsbrunner and Shi 3D convex hull is used, but for the special case when the point set lies on either a sphere or a paraboloid. Our variant greatly reduces the constant costs from the 3D convex hull algorithm and seems to be a more promising for a practical implementation than other parallel approaches. We have run experiments on the algorithm using a variety of distributions that are motivated by various problems that use Delau...

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