About: Polygonalization

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

thumbnail
Property Value
dbo:abstract
  • In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle. Every point set that does not lie on a single line has at least one polygonalization, which can be found in polynomial time. For points in convex position, there is only one, but for some other point sets there can be exponentially many. Finding an optimal polygonalization under several natural optimization criteria is a hard problem, including as a special case the travelling salesman problem. The complexity of counting all polygonalizations remains unknown. (en)
dbo:thumbnail
dbo:wikiPageID
  • 64258213 (xsd:integer)
dbo:wikiPageLength
  • 22587 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1111377755 (xsd:integer)
dbo:wikiPageWikiLink
dbp:cs1Dates
  • ly (en)
dbp:date
  • August 2022 (en)
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle. (en)
rdfs:label
  • Polygonalization (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License