This HTML5 document contains 39 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/
n8https://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#
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Jump-and-Walk_algorithm
Subject Item
dbr:List_of_numerical_analysis_topics
dbo:wikiPageWikiLink
dbr:Jump-and-Walk_algorithm
Subject Item
dbr:Jump-and-Walk_algorithm
rdf:type
yago:WikicatAlgorithms yago:Rule105846932 yago:YagoPermanentlyLocatedEntity yago:PsychologicalFeature100023100 yago:Activity100407535 yago:Act100030358 yago:Abstraction100002137 yago:Procedure101023820 dbo:Software yago:Algorithm105847438 yago:Event100029378
rdfs:label
Jump-and-Walk algorithm
rdfs:comment
Jump-and-Walk is an algorithm for point location in triangulations (though most of the theoretical analysis were performed in 2D and 3D random Delaunay triangulations). Surprisingly, the algorithm does not need any preprocessing or complex data structures except some simple representation of the triangulation itself. The predecessor of Jump-and-Walk was due to Lawson (1977) and Green and Sibson (1978), which picks a random starting point S and then walks from S toward the query point Q one triangle at a time. But no theoretical analysis was known for these predecessors until after mid-1990s.
dcterms:subject
dbc:Algorithms dbc:Triangulation_(geometry)
dbo:wikiPageID
13830115
dbo:wikiPageRevisionID
1117724057
dbo:wikiPageWikiLink
dbr:Delaunay_triangulation dbr:Symposium_on_Computational_Geometry dbr:Algorithmica dbr:Triangulation dbr:Point_location dbr:Computational_Geometry_(journal) dbc:Algorithms dbr:Algorithm dbc:Triangulation_(geometry)
owl:sameAs
yago-res:Jump-and-Walk_algorithm wikidata:Q6311028 n8:4or2p freebase:m.03ckkd_
dbp:wikiPageUsesTemplate
dbt:Citation
dbo:abstract
Jump-and-Walk is an algorithm for point location in triangulations (though most of the theoretical analysis were performed in 2D and 3D random Delaunay triangulations). Surprisingly, the algorithm does not need any preprocessing or complex data structures except some simple representation of the triangulation itself. The predecessor of Jump-and-Walk was due to Lawson (1977) and Green and Sibson (1978), which picks a random starting point S and then walks from S toward the query point Q one triangle at a time. But no theoretical analysis was known for these predecessors until after mid-1990s. Jump-and-Walk picks a small group of sample points and starts the walk from the sample point which is the closest to Q until the simplex containing Q is found. The algorithm was a folklore in practice for some time, and the formal presentation of the algorithm and the analysis of its performance on 2D random Delaunay triangulation was done by Devroye, Mucke and Zhu in mid-1990s (the paper appeared in Algorithmica, 1998). The analysis on 3D random Delaunay triangulation was done by Mucke, Saias and Zhu (ACM Symposium of Computational Geometry, 1996). In both cases, a boundary condition was assumed, namely, Q must be slightly away from the boundary of the convex domain where the vertices of the random Delaunay triangulation are drawn. In 2004, Devroye, Lemaire and Moreau showed that in 2D the boundary condition can be withdrawn (the paper appeared in Computational Geometry: Theory and Applications, 2004). Jump-and-Walk has been used in many famous software packages, e.g., QHULL, Triangle and CGAL.
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Jump-and-Walk_algorithm?oldid=1117724057&ns=0
dbo:wikiPageLength
3699
foaf:isPrimaryTopicOf
wikipedia-en:Jump-and-Walk_algorithm
Subject Item
wikipedia-en:Jump-and-Walk_algorithm
foaf:primaryTopic
dbr:Jump-and-Walk_algorithm