About: Polygon covering

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

About: Polygon covering Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatPolygons, 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%2FPolygon_covering&invfp=IFP_OFF&sas=SAME_AS_OFF

In geometry, a covering of a polygon is a set of primitive units (e.g. squares) whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

Attributes	Values
rdf:type	yago:Abstraction100002137 yago:Attribute100024264 yago:Figure113862780 yago:PlaneFigure113863186 yago:Polygon113866144 yago:Shape100027807 yago:WikicatPolygons
rdfs:label	Polygon covering (en)
rdfs:comment	In geometry, a covering of a polygon is a set of primitive units (e.g. squares) whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon. (en)
foaf:depiction
dcterms:subject	Polygons Computational geometry Covering problems
Wikipage page ID	43043289 (xsd:integer)
Wikipage revision ID	1108005476 (xsd:integer)
Link from a Wikipage to another Wikipage	Polygons Vertex cover General position Geometry NP-hard Pseudotriangle Star of David Steiner point (computational geometry) Steiner tree problem Clique cover Computational geometry Perfect graph Polygon Simple polygon Star polygon Spiral Computational geometry Packing problems Tessellation Rectilinear polygon Intersection graph Covering problems Art gallery problem Polygon triangulation 3SAT Covering problems Set cover problem Union (set theory) Existential theory of the reals Polygon partition Orthogonally convex Tree graph APX-hard dbr:Anti_rectangle
sameAs	Polygon covering Polygon covering Polygon covering Polygon covering
dbp:wikiPageUsesTemplate	dbt:Main dbt:Mvar dbt:Ordered_list dbt:Radic dbt:Reflist dbt:Short_description
thumbnail	wiki-commons:Special:FilePath/Removing_holes_from_a_rectilinear_polygon.png?width=300
has abstract	In geometry, a covering of a polygon is a set of primitive units (e.g. squares) whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon. In some scenarios, it is not required to cover the entire polygon but only its edges (this is called polygon edge covering) or its vertices (this is called polygon vertex covering). In a covering problem, the units in the covering are allowed to overlap, as long as their union is exactly equal to the target polygon. This is in contrast to a packing problem, in which the units must be disjoint and their union may be smaller than the target polygon, and to a polygon partition problem, in which the units must be disjoint and their union must be equal to the target polygon. A polygon covering problem is a special case of the set cover problem. In general, the problem of finding a smallest set covering is NP-complete, but for special classes of polygons, a smallest polygon time. A covering of a polygon P is a collection of maximal units, possibly overlapping, whose union equals P. A minimal covering is a covering that does not contain any other covering (i.e. it is a local minimum). A minimum covering is a covering with a smallest number of units (i.e. a global minimum). Every minimum covering is minimal, but not vice versa. (en)
gold:hypernym	Set
prov:wasDerivedFrom	wikipedia-en:Polygon_covering?oldid=1108005476&ns=0
page length (characters) of wiki page	16989 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Polygon_covering
is Link from a Wikipage to another Wikipage of	Covering number Rectilinear polygon Art gallery problem Polygon triangulation Polygon partition
is foaf:primaryTopic of	wikipedia-en:Polygon_covering

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, 50 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software