Highway Hull Revisited

Simple item page
dc.creatorAloupis, Greg
dc.creatorCardinal, Jean
dc.creatorCollette, Sebastien
dc.creatorHurtado, Ferran
dc.creatorLangerman, Stefan
dc.creatorO'Rourke, Joseph
dc.creatorPalop, Belen
dc.date2008-06-09
dc.date2009-04-22
dc.date.accessioned2026-07-07T13:06:33Z
dc.date.available2026-07-07T13:06:33Z
dc.descriptionA highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of points is the minimum time required to move from one point to the other, with optional use of H. The highway hull HH(S,H) of a point set S is the minimal set containing S as well as the shortest paths between all pairs of points in HH(S,H), using the highway time distance. We provide a Theta(n log n) worst-case time algorithm to find the highway hull under the L_1 metric, as well as an O(n log^2 n) time algorithm for the L_2 metric which improves the best known result of O(n^2). We also define and construct the useful region of the plane: the region that a highway must intersect in order that the shortest path between at least one pair of points uses the highway.
dc.identifierhttps://arxiv.org/abs/0806.1416
dc.identifierhttp://arxiv.org/abs/0806.1416
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/227818
dc.subjectComputational Geometry
dc.titleHighway Hull Revisited
dc.typetext

Files

Collections

arXiv