## Abstract

We consider the problem of computing the time-convex hull of a point set under the general L_{p} 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 L_{p} metric in optimal O(n log n) time for a given set of n points and a real number p with 1 ≤ p ≤ ∞.

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

Title of host publication | Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings |

Pages | 268-279 |

Number of pages | 12 |

DOIs | |

State | Published - 2013 |

Event | 13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada Duration: 12 Aug 2013 → 14 Aug 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8037 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 13th International Symposium on Algorithms and Data Structures, WADS 2013 |
---|---|

Country/Territory | Canada |

City | London, ON |

Period | 12/08/13 → 14/08/13 |

## Fingerprint

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