Home›Computational Geometry Algorithm›All Computational Geometry AlgorithmBrowse ByAll Computational Geometry AlgorithmReference and ClassificationDevelopingA named algorithm operating on geometric objects such as points, lines and polygons, computing a geometric structure or property. Belongs here: Graham Scan Algorithm, which computes the convex hull of a set of points. Does not belong here: a numerical algorithm that happens to use coordinates or matrices without computing a geometric structure, filed under Numerical Algorithm.FactsAll Computational Geometry AlgorithmSourcesComments (0)Reader Challenges (0)FactsComparisonEra of EmergenceWell-attested1975 CE 1All Computational Geometry AlgorithmFilter Results47 entriesCategoryAllConvex Hull Algorithms (5)Curve Simplification and Smoothing Algorithms (2)Geometric Intersection, Proximity and Measurement Algorithms (4)Image Feature Detection Algorithms (3)Line Drawing and Clipping Algorithms (7)Spatial Index Structures (4)Triangulation, Voronoi and Mesh Algorithms (7)Time ComplexityAllO((n+k) log n) (1)O(n log h) (1)O(n log n) (1)O(N log N) typical, O(N squared) in degenerate cases (1)O(n) to compute the diameter of a convex polygon (1)Credited ToAllDanny Cohen (1)David G. Lowe (1)David P. Dobkin (1)Edwin Catmull (1)Ivan Sutherland (1)Jim Clark (1)Jon Bentley (1)Ronald Graham (1)Timothy M. Chan (1)ACM AreaAllAlgorithms and Complexity Theory (18)Computer Algebra (1)Computer Graphics (9)Computer Vision (3)GroupAllConvex Hull Algorithms (5)Curve Simplification and Smoothing Algorithms (2)Geometric Intersection, Proximity and Measurement Algorithms (4)Image Feature Detection Algorithms (3)Line Drawing and Clipping Algorithms (7)Spatial Index Structures (4)Triangulation, Voronoi and Mesh Algorithms (7)Invented ByAllDanny Cohen (1)David G. Lowe (1)David P. Dobkin (1)Edwin Catmull (1)Ivan Sutherland (2)Jack E. Bresenham (1)Jim Clark (1)Jon Bentley (1)Ronald Graham (1)Timothy M. Chan (1)Design TechniqueAllDivide and Conquer (3)Greedy (1)Heuristic or Approximation (2)Show ResultsBrowseCompareSelect all 47Bentley-Ottmann AlgorithmComputational Geometry AlgorithmBowyer-Watson AlgorithmComputational Geometry AlgorithmBresenham's Line AlgorithmComputational Geometry AlgorithmCatmull-Clark Subdivision AlgorithmComputational Geometry AlgorithmChaikin's AlgorithmComputational Geometry AlgorithmChan's AlgorithmComputational Geometry AlgorithmClosest Pair of Points AlgorithmComputational Geometry AlgorithmCohen-Sutherland AlgorithmComputational Geometry AlgorithmCoresetComputational Geometry AlgorithmDe Casteljau's AlgorithmComputational Geometry AlgorithmDigital Differential Analyzer AlgorithmComputational Geometry AlgorithmFarthest-First TraversalComputational Geometry AlgorithmFortune's AlgorithmComputational Geometry AlgorithmGilbert-Johnson-Keerthi Distance AlgorithmComputational Geometry AlgorithmGraham Scan AlgorithmComputational Geometry AlgorithmHarris Corner Detector AlgorithmComputational Geometry AlgorithmHistogram of Oriented Gradients AlgorithmComputational Geometry AlgorithmHough Transform AlgorithmComputational Geometry AlgorithmJarvis March AlgorithmComputational Geometry AlgorithmK-d Tree AlgorithmComputational Geometry AlgorithmKirkpatrick-Seidel AlgorithmComputational Geometry AlgorithmLiang-Barsky AlgorithmComputational Geometry AlgorithmLloyd's AlgorithmComputational Geometry AlgorithmMarching Cubes AlgorithmComputational Geometry AlgorithmMarching Squares AlgorithmComputational Geometry AlgorithmMidpoint Circle AlgorithmComputational Geometry AlgorithmNewest Vertex BisectionComputational Geometry AlgorithmNon-Maximum Suppression AlgorithmComputational Geometry AlgorithmOctree AlgorithmComputational Geometry AlgorithmOriented FAST and Rotated BRIEF AlgorithmComputational Geometry AlgorithmPlotting algorithms for the Mandelbrot setComputational Geometry AlgorithmPoint in Polygon AlgorithmComputational Geometry AlgorithmPolygon Triangulation AlgorithmComputational Geometry AlgorithmQuadtree AlgorithmComputational Geometry AlgorithmQuickhull AlgorithmComputational Geometry AlgorithmRamer-Douglas-Peucker AlgorithmComputational Geometry AlgorithmRotating CalipersComputational Geometry AlgorithmR-Tree AlgorithmComputational Geometry AlgorithmScale-Invariant Feature Transform AlgorithmComputational Geometry AlgorithmShoelace FormulaComputational Geometry AlgorithmSnap RoundingComputational Geometry AlgorithmSpeeded Up Robust Features AlgorithmComputational Geometry AlgorithmSutherland-Hodgman AlgorithmComputational Geometry AlgorithmVisvalingam-Whyatt AlgorithmComputational Geometry AlgorithmWeiler-Atherton AlgorithmComputational Geometry AlgorithmWelzl's AlgorithmComputational Geometry AlgorithmXiaolin Wu's line algorithmComputational Geometry AlgorithmSources1. Wikipedia: Computational geometrytier 2WikipediaComputational geometry, lead section, term-origin sentenceQuote, Computational geometry, lead section, term-origin sentenceA groundlaying book in the subject by Preparata and Shamos dates the first use of the term "computational geometry" in this sense by 1975.View the SourceComments (0)No comments yet. Be the first to share a thought.Sign in to join the discussion.Reader Challenges (0)No disputes yet. Spotted an error or a better source? Open the first one.Sign in to dispute this or suggest a correction.