Share
VIDEOS 1 TO 50
Computational Geometry I
Computational Geometry I
Published: 2015/12/29
Channel: Wolfram
CGAL: The Open Source Computational Geometry Algorithms Library
CGAL: The Open Source Computational Geometry Algorithms Library
Published: 2008/03/13
Channel: GoogleTechTalks
What is COMPUTATIONAL GEOMETRY? What does COMPUTATIONAL GEOMETRY mean?
What is COMPUTATIONAL GEOMETRY? What does COMPUTATIONAL GEOMETRY mean?
Published: 2017/02/20
Channel: The Audiopedia
CENG773 - Computational Geometry - Lecture 1.1
CENG773 - Computational Geometry - Lecture 1.1
Published: 2015/04/15
Channel: METUOpenCourseWare
Algorithms } 040 } Computational Geometry } Line Segments }
Algorithms } 040 } Computational Geometry } Line Segments }
Published: 2016/05/03
Channel: Leprofesseur }
MIT 6.006 Fall 2011 Lecture 24
MIT 6.006 Fall 2011 Lecture 24
Published: 2013/01/03
Channel: Victor Costan
Computational Geometry Final Project MIT
Computational Geometry Final Project MIT
Published: 2014/05/16
Channel: Masha Shugrina
Computational Geometry Lecture 13: Delaunay triangulations and Voronoi diagrams
Computational Geometry Lecture 13: Delaunay triangulations and Voronoi diagrams
Published: 2014/11/10
Channel: Mikola Lysenko
Python Powered Computational Geometry
Python Powered Computational Geometry
Published: 2012/08/22
Channel: PyCon Australia
Computational Geometry Lecture 21: Well-separated pair decompositions
Computational Geometry Lecture 21: Well-separated pair decompositions
Published: 2014/11/25
Channel: Mikola Lysenko
Computational Geometry Lecture 19: Interval, segment and priority search trees
Computational Geometry Lecture 19: Interval, segment and priority search trees
Published: 2014/11/21
Channel: Mikola Lysenko
Computational Geometry Lecture 14: Point location and trapezoidal decompositions
Computational Geometry Lecture 14: Point location and trapezoidal decompositions
Published: 2014/11/10
Channel: Mikola Lysenko
Tyler Reddy - Computational Geometry in Python - PyCon 2016
Tyler Reddy - Computational Geometry in Python - PyCon 2016
Published: 2016/05/30
Channel: PyCon 2016
CENG773 - Computational Geometry - Lecture 4.1
CENG773 - Computational Geometry - Lecture 4.1
Published: 2015/04/16
Channel: METUOpenCourseWare
Computational Geometry Lec 5 Part 1
Computational Geometry Lec 5 Part 1
Published: 2016/04/09
Channel: ahmed sayed
Computational Geometry Lecture 15: Line segment intersection and persistence
Computational Geometry Lecture 15: Line segment intersection and persistence
Published: 2014/11/10
Channel: Mikola Lysenko
Computational Geometry Lecture 1:  Review of linear algebra
Computational Geometry Lecture 1: Review of linear algebra
Published: 2014/11/10
Channel: Mikola Lysenko
CENG773 - Computational Geometry - Lecture 6.1
CENG773 - Computational Geometry - Lecture 6.1
Published: 2015/04/16
Channel: METUOpenCourseWare
Computational Geometry: Line Segment Properties ( Two lines Clockwise or Counterclockwise)
Computational Geometry: Line Segment Properties ( Two lines Clockwise or Counterclockwise)
Published: 2014/08/12
Channel: saurabhschool
Computational Geometry Lecture 16: Polygon triangulation
Computational Geometry Lecture 16: Polygon triangulation
Published: 2014/11/10
Channel: Mikola Lysenko
Python Powered Computational Geometry
Python Powered Computational Geometry
Published: 2012/04/30
Channel: Andrew Walker
Computational geometry algorithms for machine learning
Computational geometry algorithms for machine learning
Published: 2012/07/18
Channel: compcinemaucsc
Extended Principle of Mathematical Induction: Example from computational geometry (Screencast 4.2.2)
Extended Principle of Mathematical Induction: Example from computational geometry (Screencast 4.2.2)
Published: 2012/10/09
Channel: GVSUmath
Computational Geometry Lecture 23: Motion planning
Computational Geometry Lecture 23: Motion planning
Published: 2014/12/05
Channel: Mikola Lysenko
Computational Geometry Lecture 9: Cell complexes
Computational Geometry Lecture 9: Cell complexes
Published: 2014/11/10
Channel: Mikola Lysenko
Computational Geometry Lecture 2: Affine and projective spaces
Computational Geometry Lecture 2: Affine and projective spaces
Published: 2014/11/10
Channel: Mikola Lysenko
Geometric Madness with Jason Davies
Geometric Madness with Jason Davies
Published: 2014/10/02
Channel: John Wilson
Computational Geometry Lecture 4: Convex hulls in 2D
Computational Geometry Lecture 4: Convex hulls in 2D
Published: 2014/11/10
Channel: Mikola Lysenko
Computational Geometry Lecture 12: Data structures for linear programming
Computational Geometry Lecture 12: Data structures for linear programming
Published: 2014/11/10
Channel: Mikola Lysenko
Computational Geometry Lecture 11: Higher dimensional convex hulls
Computational Geometry Lecture 11: Higher dimensional convex hulls
Published: 2014/11/10
Channel: Mikola Lysenko
Introduction to Graph Laplacian and Computational Geometry
Introduction to Graph Laplacian and Computational Geometry
Published: 2017/05/26
Channel: NCTS Math Division
Computational Geometry - 01 (Arabic)
Computational Geometry - 01 (Arabic)
Published: 2013/04/25
Channel: Arabic Competitive Programming
CENG773 - Computational Geometry - Lecture 8.1
CENG773 - Computational Geometry - Lecture 8.1
Published: 2015/04/16
Channel: METUOpenCourseWare
Conference on Computational Mathematics, Computational Geometry & Statistics
Conference on Computational Mathematics, Computational Geometry & Statistics
Published: 2014/02/24
Channel: Global Science and Technology Forum
Computational Geometry Lecture 18: Dynamization and fractional cascading
Computational Geometry Lecture 18: Dynamization and fractional cascading
Published: 2014/11/17
Channel: Mikola Lysenko
Computational Geometry Lecture 20: The closest pair problem
Computational Geometry Lecture 20: The closest pair problem
Published: 2014/11/25
Channel: Mikola Lysenko
Convex Hull - Computational Geometry
Convex Hull - Computational Geometry
Published: 2009/12/06
Channel: MorleyAbbott
Computational Geometry Lecture 10: Topological data structures
Computational Geometry Lecture 10: Topological data structures
Published: 2014/11/10
Channel: Mikola Lysenko
Computational Geometry Lecture 17: Orthogonal range searching
Computational Geometry Lecture 17: Orthogonal range searching
Published: 2014/11/17
Channel: Mikola Lysenko
CENG773 - Computational Geometry - Lecture 10.2
CENG773 - Computational Geometry - Lecture 10.2
Published: 2015/04/16
Channel: METUOpenCourseWare
LiveCG - Interactive Visualization Environment for Computational Geometry
LiveCG - Interactive Visualization Environment for Computational Geometry
Published: 2014/05/23
Channel: Sebastian Kürten
Computational Geometry Lecture 3: Convexity and orientability
Computational Geometry Lecture 3: Convexity and orientability
Published: 2014/11/10
Channel: Mikola Lysenko
Benjamin Koren - 1:One | Computational Geometry
Benjamin Koren - 1:One | Computational Geometry
Published: 2015/09/18
Channel: AA School of Architecture
Computational Geometry Lec 2
Computational Geometry Lec 2
Published: 2016/02/27
Channel: ahmed sayed
Computational Geometry - Circles (Arabic)
Computational Geometry - Circles (Arabic)
Published: 2016/10/30
Channel: Arabic Competitive Programming
Some examples 2D in Computational Geometry
Some examples 2D in Computational Geometry
Published: 2011/04/15
Channel: josuehmachado
Algorithms - Computational Geometry - 02
Algorithms - Computational Geometry - 02
Published: 2013/04/28
Channel: Mohammad Kotb
[2016資訊之芽] Computational Geometry
[2016資訊之芽] Computational Geometry
Published: 2016/05/21
Channel: ntucsiesprout
CSE 232 Lecture 8 - Computational Geometry
CSE 232 Lecture 8 - Computational Geometry
Published: 2014/10/29
Channel: Brett Olsen
Computational Geometry Lecture 22: Quad trees
Computational Geometry Lecture 22: Quad trees
Published: 2014/12/05
Channel: Mikola Lysenko
NEXT
GO TO RESULTS [51 .. 100]

WIKIPEDIA ARTICLE

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with history stretching back to antiquity.

Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(n2) and O(n log n) may be the difference between days and seconds of computation.

The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature, and may come from mathematical visualization.

Other important applications of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (mesh generation), computer vision (3D reconstruction).

The main branches of computational geometry are:

  • Combinatorial computational geometry, also called algorithmic geometry, which deals with geometric objects as discrete entities. A groundlaying book in the subject by Preparata and Shamos dates the first use of the term "computational geometry" in this sense by 1975.[1]
  • Numerical computational geometry, also called machine geometry, computer-aided geometric design (CAGD), or geometric modeling, which deals primarily with representing real-world objects in forms suitable for computer computations in CAD/CAM systems. This branch may be seen as a further development of descriptive geometry and is often considered a branch of computer graphics or CAD. The term "computational geometry" in this meaning has been in use since 1971.[2]

Combinatorial computational geometry[edit]

The primary goal of research in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc.

Some of these problems seem so simple that they were not regarded as problems at all until the advent of computers. Consider, for example, the Closest pair problem:

  • Given n points in the plane, find the two with the smallest distance from each other.

One could compute the distances between all the pairs of points, of which there are n(n-1)/2, then pick the pair with the smallest distance. This brute-force algorithm takes O(n2) time; i.e. its execution time is proportional to the square of the number of points. A classic result in computational geometry was the formulation of an algorithm that takes O(n log n). Randomized algorithms that take O(n) expected time,[3] as well as a deterministic algorithm that takes O(n log log n) time,[4] have also been discovered.

Problem classes[edit]

The core problems in computational geometry may be classified in different ways, according to various criteria. The following general classes may be distinguished.

Static problems[edit]

In the problems of this category, some input is given and the corresponding output needs to be constructed or found. Some fundamental problems of this type are:

The computational complexity for this class of problems is estimated by the time and space (computer memory) required to solve a given problem instance.

Geometric query problems[edit]

In geometric query problems, commonly known as geometric search problems, the input consists of two parts: the search space part and the query part, which varies over the problem instances. The search space typically needs to be preprocessed, in a way that multiple queries can be answered efficiently.

Some fundamental geometric query problems are:

  • Range searching: Preprocess a set of points, in order to efficiently count the number of points inside a query region.
  • Point location: Given a partitioning of the space into cells, produce a data structure that efficiently tells in which cell a query point is located.
  • Nearest neighbor: Preprocess a set of points, in order to efficiently find which point is closest to a query point.
  • Ray tracing: Given a set of objects in space, produce a data structure that efficiently tells which object a query ray intersects first.

If the search space is fixed, the computational complexity for this class of problems is usually estimated by:

  • the time and space required to construct the data structure to be searched in
  • the time (and sometimes an extra space) to answer queries.

For the case when the search space is allowed to vary, see "Dynamic problems".

Dynamic problems[edit]

Yet another major class is the dynamic problems, in which the goal is to find an efficient algorithm for finding a solution repeatedly after each incremental modification of the input data (addition or deletion input geometric elements). Algorithms for problems of this type typically involve dynamic data structures. Any of the computational geometric problems may be converted into a dynamic one, at the cost of increased processing time. For example, the range searching problem may be converted into the dynamic range searching problem by providing for addition and/or deletion of the points. The dynamic convex hull problem is to keep track of the convex hull, e.g., for the dynamically changing set of points, i.e., while the input points are inserted or deleted.

The computational complexity for this class of problems is estimated by:

  • the time and space required to construct the data structure to be searched in
  • the time and space to modify the searched data structure after an incremental change in the search space
  • the time (and sometimes an extra space) to answer a query.

Variations[edit]

Some problems may be treated as belonging to either of the categories, depending on the context. For example, consider the following problem.

  • Point in polygon: Decide whether a point is inside or outside a given polygon.

In many applications this problem is treated as a single-shot one, i.e., belonging to the first class. For example, in many applications of computer graphics a common problem is to find which area on the screen is clicked by a pointer. However, in some applications the polygon in question is invariant, while the point represents a query. For example, the input polygon may represent a border of a country and a point is a position of an aircraft, and the problem is to determine whether the aircraft violated the border. Finally, in the previously mentioned example of computer graphics, in CAD applications the changing input data are often stored in dynamic data structures, which may be exploited to speed-up the point-in-polygon queries.

In some contexts of query problems there are reasonable expectations on the sequence of the queries, which may be exploited either for efficient data structures or for tighter computational complexity estimates. For example, in some cases it is important to know the worst case for the total time for the whole sequence of N queries, rather than for a single query. See also "amortized analysis".

Numerical computational geometry[edit]

This branch is also known as geometric modelling and computer-aided geometric design (CAGD).

Core problems are curve and surface modelling and representation.

The most important instruments here are parametric curves and parametric surfaces, such as Bézier curves, spline curves and surfaces. An important non-parametric approach is the level set method.

Application areas include shipbuilding, aircraft, and automotive industries. The modern ubiquity and power of computers means that even perfume bottles and shampoo dispensers are designed using techniques unheard of by shipbuilders of the 1960s.

See also[edit]

References[edit]

  1. ^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3. 
  2. ^ A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187-195 (1971)
  3. ^ S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995
  4. ^ S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979

Further reading[edit]

Journals[edit]

Combinatorial/algorithmic computational geometry[edit]

Below is the list of the major journals that have been publishing research in geometric algorithms. Please notice with the appearance of journals specifically dedicated to computational geometry, the share of geometric publications in general-purpose computer science and computer graphics journals decreased.

External links[edit]

Disclaimer

None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Powered by YouTube
Wikipedia content is licensed under the GFDL and (CC) license