## Abstract

We consider the problem of computing the time-convex hull of a point set under the general _{Lp} metric in the presence of a straight-line highway in the plane. The traveling speed along the highway is assumed to be faster than that off the highway, and the shortest time-path between a distant pair may involve traveling along the highway. The time-convex hull TCH(P) of a point set P is the smallest set containing both P and all shortest time-paths between any two points in TCH(P). In this paper we give an algorithm that computes the time-convex hull under the _{Lp} metric in optimal O(nlogn) time for a given set of n points and a real number p with 1 < > < >;≤.

Original language | English |
---|---|

Pages (from-to) | 1-20 |

Number of pages | 20 |

Journal | Computational Geometry: Theory and Applications |

Volume | 53 |

DOIs | |

State | Published - 1 Feb 2016 |

## Keywords

- -metrics
- Optimal convex hull
- Time distance

## Fingerprint

Dive into the research topics of 'Optimal time-convex hull for a straight-line highway in L_{p}-metrics'. Together they form a unique fingerprint.