Many geometric problems like generalized Voronoi diagrams, medial axis computations and boundary evaluation involve computation and manipulation of non-linear algebraic primitives like curves and surfaces. The algorithms designed for these problems make decisions based on signs of geometric predicates or on the roots of polynomials characterizing the problem. The reliability of the algorithm depends on the accurate evaluation of these signs and roots. In this paper, we present a {\em naive precision-driven computational model} to perform these computations reliably and demonstrate its effectiveness on a certain class of problems like sign of determinants with rational entries, boundary evaluation and curve arrangements. We also present a novel algorithm to compute all the roots of a univariate polynomial to any desired accuracy. The computational model along with the underlying number representation, precision-driven arithmetic and all the algorithms are implemented as part of a stand-alone software library, PRECISE.

No abstract available.

We present techniques for fast motion planning by using discrete approximations of generalized Voronoi diagrams, computed with graphics hardware. Approaches based on this diagram computation are applicable to both static and dynamic environments of fairly high complexity. We compute a discrete Voronoi diagram by rendering a 3D distance mesh for each Voronoi site. The sites can be points, line segments, polygons, polyhedra, curves and surfaces. The computation of the generalized Voronoi diagram provides fast proximity query toolkits for motion planning. The tools provide the distance to the nearest obstacle stored in the Z-buffer, as well as the Voronoi boundaries, Voronoi vertices and weighted Voronoi graphs extracted from the frame buffer using continuation methods. We have implemented these algorithms and demonstrated their performance for path planning in a complex dynamic environment composed of more than 140,000 polygons.

We present MAPC, a library for exact representation of geometric objects-specifically points and algebraic curves in the plane.Our library makes use of several new algorithms, which we present here, including methods for fmding the sign of a determinant, fmding intersections between two curves, and breaking a curve into monotonic segments.These algorithms are used to speed up the underlying computations.The library provides C++ classes that can be used to easily instantiate, manipulate, and perform queries on points and curves in the plane.The point classes can be used to represent points known in a variety of.ways (e.g. as exact rational coordinates or algebraic numbers) in a unified manner.The curve class can be used to represent a portion of an algebraic curve.We have used MAPC for applications dealing with algebraic points and curves, including sorting points along a curve, computing arrangement of curves, medial axis computations, and boundary' evaluation on curved primitives.As compared to earlier algorithms and implementations utilizing exact arithmetic, our library is able to achieve more than an order of magnitude improvement in performance.

Article Fast computation of generalized Voronoi diagrams using graphics hardware Share on Authors: Kenneth E. Hoff University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , John Keyser University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Ming Lin University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Dinesh Manocha University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Tim Culver University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile Authors Info & Claims SIGGRAPH '99: Proceedings of the 26th annual conference on Computer graphics and interactive techniquesJuly 1999 Pages 277–286https://doi.org/10.1145/311535.311567Published:01 July 1999 311citation3,192DownloadsMetricsTotal Citations311Total Downloads3,192Last 12 Months86Last 6 weeks4 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