Content deleted Content added
No edit summary |
No edit summary |
||
Line 31:
In a grid-based approach, the bounding square of all nodes is equally subdivided into square cells.
'''How are access-nodes selected?'''
For each cell <math>C</math>, a set of access nodes can be found by looking at an inner area <math>I</math> of 5x5 cells and an outer area <math>O</math> of 9x9 cells around <math>C</math>. Focusing on crossing nodes (ends of edges that cross the boundary of <math>C</math>,<math>I</math>or <math>O</math>), the access nodes for <math>C</math>are those nodes of <math>I</math>that are part of a shortest path from some node in <math>C</math>to a node in <math>O</math>. As access nodes for an arbitrary node <math>n</math> all access nodes of the cell containing <math>n</math>are chosen.
Line 48:
=== Using Contraction Hierarchies ===
'''How are transit-nodes selected?'''
By definition, a contraction hierarchy move important nodes (i.e. nodes that are part of many shortest paths) to the top of the hierarchy. A set of transit-nodes therefore can be selected as the <math>k</math>highest nodes of the contraction hierarchy.
'''How are access-nodes selected?'''
Forward access-nodes of a node <math>n</math>can be found by running the upward-phase of the contraction hierarchy starting at <math>n</math>. During the upward-phase, edges leaving previously found transit nodes aren't relaxed. When the search has no more upward nodes left to settle, those transit nodes that have been settled are the access-nodes of <math>n</math>. Backward access-nodes can be found analogously.
'''Which locality filter should be used?'''
'''How should local queries be handled?'''
== See also ==
| |||