Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU

Simple item page
dc.contributor.authorReischl, Maximilianen_US
dc.contributor.authorKnauer, Christianen_US
dc.contributor.authorGuthe, Michaelen_US
dc.contributor.editorLee, Sung-hee and Zollmann, Stefanie and Okabe, Makoto and Wuensche, Burkharden_US
dc.date.accessioned2020-10-29T18:39:38Z
dc.date.available2020-10-29T18:39:38Z
dc.date.issued2020
dc.description.abstractWe present a new approach for path finding in weighted graphs using pre-computed minimal distance fields. By selecting the most promising minimal distance field at any given node and switching between them, our algorithm tries to find the shortest path. As we show, this approach scales very well for different topologies, hardware and graph sizes and has a mean length error below 1% while using reasonable amounts of memory. By keeping a simple structure and minimal backtracking, we are able to use the same approach on the massively parallel GPU, reducing the run time even further.en_US
dc.description.sectionheadersGeometric Computations
dc.description.seriesinformationPacific Graphics Short Papers, Posters, and Work-in-Progress Papers
dc.identifier.doi10.2312/pg.20201228
dc.identifier.isbn978-3-03868-120-5
dc.identifier.pages37-42
dc.identifier.urihttps://doi.org/10.2312/pg.20201228
dc.identifier.urihttps://diglib.eg.org:443/handle/10.2312/pg20201228
dc.publisherThe Eurographics Associationen_US
dc.subjectTheory of computation
dc.subjectGraph algorithms analysis
dc.subjectComputational geometry
dc.subjectMathematics of computing
dc.subjectGraph algorithms
dc.titleUsing Landmarks for Near-Optimal Pathfinding on the CPU and GPUen_US
Files
Collections
PG2020 Short Papers, Posters, and Work-in-Progress Papers