List of NP-complete Problems - Computational Geometry

Computational Geometry

  • Testing whether a tree may be represented as Euclidean minimum spanning tree
  • Unit disk graph recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane)
  • Many motion planning among polygonal obstacles in the plane are NP-hard.
    • Planar partitioning into connected subassemblies: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from AS by a collision-free rigid motion of S, and such that both S and AS are connected.
  • Art gallery problem and its variations.

Read more about this topic:  List Of NP-complete Problems

Other articles related to "computational geometry, computational":

Numerical Computational Geometry
... Core problems are curve and surface modelling and representation ... The most important instruments here are parametric curves and parametric surfaces, such as Bezier curves, spline curves and surfaces ...
List Of Books In Computational Geometry - Conferences
... Annual Symposium on Computational Geometry (SoCG) Canadian Conference on Computational Geometry (CCCG) Japanese Conference on Discrete and Computational Geometry (JCDCG) The conferences below, of broad scope ...
List Of Books In Computational Geometry - Combinatorial Computational Geometry - References
... Handbook of Discrete and Computational Geometry ... to Algorithms, in its comprehensiveness, only restricted to discrete and computational geometry, computational topology, as well as a broad range of their ... Handbook of Computational Geometry ...
List Of Books In Computational Geometry - Numerical Computational Geometry (geometric Modelling, Computer-aided Geometric Design) - Monographs
... Computational Geometry for Design and Manufacture (Mathematics Its Applications) ... An Introduction to Computational Geometry for Curves and Surfaces ... Effective Computational Geometry for Curves and Surfaces (Mathematics and Visualization Series ed.) ...
List Of Books In Computational Geometry
... This is a list of books in computational geometry ... two major, largely nonoverlapping categories Combinatorial computational geometry, which deals with collections of discrete objects or defined in discrete terms points, lines, polygons, polytopes, etc ... of discrete/combinatorial character are used Numerical computational geometry, also known as geometric modeling and computer-aided geometric design (CAGD), which deals with modelling of shapes ...

Famous quotes containing the word geometry:

    ... geometry became a symbol for human relations, except that it was better, because in geometry things never go bad. If certain things occur, if certain lines meet, an angle is born. You cannot fail. It’s not going to fail; it is eternal. I found in rules of mathematics a peace and a trust that I could not place in human beings. This sublimation was total and remained total. Thus, I’m able to avoid or manipulate or process pain.
    Louise Bourgeois (b. 1911)