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 (K-CPQ) 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 non-convex k-fat 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 multi-dimensional data; efficient insert, delete, location, approximate range, approximate nearest neighbor; logarithmic-height search and update [»eppsD6_2005]
|
Subtopic: space filling curve
| Quote: the UB-Tree uses a space-filling curve to map multidimensions into one; the Z-curve is efficiently implemented as variable length bitstrings [»ramsF9_2000, OK]
|
Subtopic: point inclusion
| Quote: fast, inclusion test for 2-d 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 d-space; floating-point 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)
|
