Optimal time-convex hull under the Lp metrics

Bang Sin Dai, Mong Jen Kao, D. T. Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

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(n log n) time for a given set of n points and a real number p with 1 ≤ p ≤ ∞.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Pages268-279
Number of pages12
DOIs
StatePublished - 2013
Event13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada
Duration: 12 Aug 201314 Aug 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8037 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Symposium on Algorithms and Data Structures, WADS 2013
Country/TerritoryCanada
CityLondon, ON
Period12/08/1314/08/13

Fingerprint

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

Cite this