This HTML5 document contains 34 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n16https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Watchman_route_problem
rdf:type
yago:Rule105846932 yago:Procedure101023820 yago:Act100030358 yago:Abstraction100002137 yago:WikicatGeometricAlgorithms yago:PsychologicalFeature100023100 yago:Activity100407535 yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Algorithm105847438 yago:Event100029378
rdfs:label
Watchman route problem
rdfs:comment
The Watchman Problem is an optimization problem in computational geometry where the objective is to compute the shortest route a watchman should take to guard an entire area with obstacles given only a map of the area. The challenge is to make sure the watchman peeks behind every corner and to determine the best order in which corners should be visited in. The problem may be solved in polynomial time when the area to be guarded is a simple polygon. The problem is NP-hard for polygons with holes, but may be approximated in polynomial time by a solution whose length is within a polylogarithmic factor of optimal.
dcterms:subject
dbc:Geometric_algorithms
dbo:wikiPageID
2997527
dbo:wikiPageRevisionID
951707009
dbo:wikiPageWikiLink
dbr:NP-hard dbr:Polynomial_time dbc:Geometric_algorithms dbr:Computational_geometry dbr:Simple_polygon dbr:Optimization_(mathematics) dbr:Art_gallery_problem
owl:sameAs
wikidata:Q7973176 yago-res:Watchman_route_problem freebase:m.08jlp3 n16:4xnKy
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Geometry-stub
dbo:abstract
The Watchman Problem is an optimization problem in computational geometry where the objective is to compute the shortest route a watchman should take to guard an entire area with obstacles given only a map of the area. The challenge is to make sure the watchman peeks behind every corner and to determine the best order in which corners should be visited in. The problem may be solved in polynomial time when the area to be guarded is a simple polygon. The problem is NP-hard for polygons with holes, but may be approximated in polynomial time by a solution whose length is within a polylogarithmic factor of optimal.
gold:hypernym
dbr:Problem
prov:wasDerivedFrom
wikipedia-en:Watchman_route_problem?oldid=951707009&ns=0
dbo:wikiPageLength
2276
foaf:isPrimaryTopicOf
wikipedia-en:Watchman_route_problem