Map Index Random Help Topics

Topic: computational geometry

topics > computer science > Group: algorithms

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)

Updated barberCB 8/05