Optimal time-convex hull under the Lp metrics

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

doi:10.1007/978-3-642-40104-6_24

Optimal time-convex hull under the L_p metrics

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

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

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	https://doi.org/10.1007/978-3-642-40104-6_24
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

Access to Document

10.1007/978-3-642-40104-6_24

Cite this

Dai, B. S., Kao, M. J., & Lee, D. T. (2013). Optimal time-convex hull under the L_p metrics. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings (pp. 268-279). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS). https://doi.org/10.1007/978-3-642-40104-6_24

@inproceedings{8f445e5d498a44e295b11531ac447218,

title = "Optimal time-convex hull under the Lp metrics",

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 ≤ ∞.",

author = "Dai, {Bang Sin} and Kao, {Mong Jen} and Lee, {D. T.}",

year = "2013",

doi = "10.1007/978-3-642-40104-6_24",

language = "English",

isbn = "9783642401039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "268--279",

booktitle = "Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings",

note = "13th International Symposium on Algorithms and Data Structures, WADS 2013 ; Conference date: 12-08-2013 Through 14-08-2013",

}

Dai, BS, Kao, MJ & Lee, DT 2013, Optimal time-convex hull under the L_p metrics. in Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8037 LNCS, pp. 268-279, 13th International Symposium on Algorithms and Data Structures, WADS 2013, London, ON, Canada, 12/08/13. https://doi.org/10.1007/978-3-642-40104-6_24

Optimal time-convex hull under the L_p metrics. / Dai, Bang Sin; Kao, Mong Jen; Lee, D. T.
Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. 2013. p. 268-279 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Optimal time-convex hull under the Lp metrics

AU - Dai, Bang Sin

AU - Kao, Mong Jen

AU - Lee, D. T.

PY - 2013

Y1 - 2013

N2 - 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 ≤ ∞.

AB - 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 ≤ ∞.

UR - http://www.scopus.com/inward/record.url?scp=84881178531&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40104-6_24

DO - 10.1007/978-3-642-40104-6_24

M3 - Conference contribution

AN - SCOPUS:84881178531

SN - 9783642401039

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

SP - 268

EP - 279

BT - Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings

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

Y2 - 12 August 2013 through 14 August 2013

ER -