Topic: computational geometry

topics > computer science > Group: algorithms


algorithmic complexity analysis
coordinate frames for robot positioning
fractal geometry
graph coloring
numerical error
probabilistic and randomized algorithms
unbounded precision


Computational geometry is not an active area for this collection. Please see for pointers.
Subtopic: geometric expressions up

Quote: in APT, assign geometric expressions to variables; for circles, lines, etc. [»browSA11_1963, OK]

Subtopic: geometric algorithms up

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 up

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 up

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 up

Quote: fast, inclusion test for 2-d points without computing convex hull; uses octant classification [»torrJC4_2000]

Subtopic: Delaunay triangulation up

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 up

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 up

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 up

Quote: represent a convex hull by slabs of coplanar vertices for each face [»cbb_1990, OK]

Subtopic: precision issues up

Quote: unrestricted geometric computation has potentially unbounded growth in the precision required [»hoffCM3_1989]

Related Topics up

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
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.