Group: mathematics
Topic: algorithmic complexity analysis
Topic: coordinate frames for robot positioning
Topic: fractal geometry
Topic: geometry
Topic: graph coloring
Topic: numerical error
Topic: probabilistic and randomized algorithms
Topic: unbounded precision
 
Summary
Computational geometry is not an active area for this collection. Please see
www.qhull.org for pointers.
Subtopic: geometric expressions
Quote: in APT, assign geometric expressions to variables; for circles, lines, etc. [»browSA11_1963, OK]
 Subtopic: geometric algorithms
Quote: measure the angle between curves by the angle between straight lines that are perpendicular to the curves at their point of intersection [»descR_1641a]
 Quote: K Closest Pairs Query (KCPQ) identifies the K pairs of spatial objects from two data sets with the smallest distances between them [»corrA5_2000]
 Quote: problem with Heller's algorithm for geographic information systems [»deviO6_1999]
 Quote: optimal, approximate range query using skip quadtrees; produces a convex or nonconvex kfat region [»eppsD6_2005]
 Subtopic: representating data
Quote: a geometric object defined by approximate data may not make sense even though it can be drawn [»hoffCM3_1989]
 Quote: to represent geometric objects can guarantee exact data, include reasoning in the computation, or alter the meaning of geometric elements [»hoffCM3_1989]
 Quote: NC machining describes curves as intersection of surfaces; used by MCL [»lozaT7_1983]
 Quote: skip quadtrees and octrees for multidimensional data; efficient insert, delete, location, approximate range, approximate nearest neighbor; logarithmicheight search and update [»eppsD6_2005]
 Subtopic: space filling curve
Quote: the UBTree uses a spacefilling curve to map multidimensions into one; the Zcurve is efficiently implemented as variable length bitstrings [»ramsF9_2000, OK]
 Subtopic: point inclusion
Quote: fast, inclusion test for 2d points without computing convex hull; uses octant classification [»torrJC4_2000]
 Subtopic: Delaunay triangulation
Quote: first practical algorithm for conforming Delaunay triangulation in 3D; adapts to local geometry; few Steiner points [»coheD_2004]
 Quote: efficient deletion of points from a Delaunay triangulation using spheres and shelling [»deviO6_1999]
 Quote: star splaying is a general dimensional edge flip; repairs nearly Delaunay triangulations and nearly convex hulls; requires general position and exact arithmetic; may be parallelized [»shewJR6_2005]
 Subtopic: arbitrary precision
Quote: arbitrary precision implementations of 2D and 3D geometric orientation and incircle tests [»shewJR5_1996]
 Quote: CORE geometric library offers guaranteed accuracy; up to 150 times slower than machine accuracy [»karaV6_1999]
 Subtopic: robust algorithms
Quote: algorithm for smallest enclosing ball in dspace; floatingpoint arthimetic; fast, robust, simple [»gartB7_1999]
 Note: joggled input allows a simple implementation of geometric algorithms [»cbb_1990, OK]
 Subtopic: imprecise convex hull
Quote: represent a convex hull by slabs of coplanar vertices for each face [»cbb_1990, OK]
 Subtopic: precision issues
Quote: unrestricted geometric computation has potentially unbounded growth in the precision required [»hoffCM3_1989]

Related Topics
Group: mathematics (23 topics, 560 quotes)
Topic: algorithmic complexity analysis (10 items)
Topic: coordinate frames for robot positioning (6 items)
Topic: fractal geometry (8 items)
Topic: geometry (33 items)
Topic: graph coloring (7 items)
Topic: numerical error (19 items)
Topic: probabilistic and randomized algorithms (11 items)
Topic: unbounded precision (9 items)
