About: Polygonalization

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Polygonalization Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FPolygonalization&invfp=IFP_OFF&sas=SAME_AS_OFF

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.

Attributes	Values
rdfs:label	Polygonalization (en)
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)
foaf:depiction
dcterms:subject	Polygons Computational geometry
Wikipage page ID	64258213 (xsd:integer)
Wikipage revision ID	1111377755 (xsd:integer)
Link from a Wikipage to another Wikipage	Monotone polygon NP (complexity) Polygons ♯P ♯P-complete General position NP-complete NP-hard Convex hull Convex position State space Linear time Computational geometry Perimeter Planar separator theorem Simple polygon Travelling salesman problem Computational geometry Cyclic order Dynamic programming E (complexity) Graham scan Graph traversal Bitonic tour Point-set triangulation Polynomial time Approximation ratio Euclidean plane Polygonal chain Reverse-search algorithm Star-shaped polygon Two ears theorem Halfplane Polynomial space
sameAs	Polygonalization Polygonalization
dbp:wikiPageUsesTemplate	dbt:Harvtxt dbt:R dbt:Reflist dbt:Short_description dbt:Use_list-defined_references dbt:Use_mdy_dates dbt:Unsolved
thumbnail	wiki-commons:Special:FilePath/16_polygonalizations.svg?width=300
cs1-dates	ly (en)
date	August 2022 (en)
has 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)
prov:wasDerivedFrom	wikipedia-en:Polygonalization?oldid=1111377755&ns=0
page length (characters) of wiki page	22587 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Polygonalization
is Link from a Wikipage to another Wikipage of	Travelling salesman problem Euclidean minimum spanning tree Graham scan Bitonic tour Reverse-search algorithm
is foaf:primaryTopic of	wikipedia-en:Polygonalization

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software