All farthest neighbors in the presence of highways and obstacles

Sang Won Bae; Matias Korman; Takeshi Tokuyama

doi:10.1007/978-3-642-00202-1_7

All farthest neighbors in the presence of highways and obstacles

Sang Won Bae, Matias Korman, Takeshi Tokuyama

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

9 Citations (Scopus)

Abstract

We consider the problem of computing all farthest neighbors (and the diameter) of a given set of n points in the presence of highways and obstacles in the plane. When traveling on the plane, travelers may use highways for faster movement and must avoid all obstacles. We present an efficient solution to this problem based on knowledge from earlier research on shortest path computation. Our algorithms run in O(nm(logm + log2 n)) time using O(m + n) space, where the m is the combinatorial complexity of the environment consisting of highways and obstacles.

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings
Pages	71-82
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-00202-1_7
Publication status	Published - 2009
Externally published	Yes
Event	3rd International Workshop on Algorithms and Computation, WALCOM 2009 - Kolkata, India Duration: 2009 Feb 18 → 2009 Feb 20

Publication series

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

Other

Other	3rd International Workshop on Algorithms and Computation, WALCOM 2009
Country/Territory	India
City	Kolkata
Period	09/2/18 → 09/2/20

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-00202-1_7

Cite this

Bae, S. W., Korman, M., & Tokuyama, T. (2009). All farthest neighbors in the presence of highways and obstacles. In WALCOM: Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings (pp. 71-82). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5431 LNCS). https://doi.org/10.1007/978-3-642-00202-1_7

All farthest neighbors in the presence of highways and obstacles. / Bae, Sang Won; Korman, Matias; Tokuyama, Takeshi.
WALCOM: Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings. 2009. p. 71-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5431 LNCS).

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

Bae, SW, Korman, M & Tokuyama, T 2009, All farthest neighbors in the presence of highways and obstacles. in WALCOM: Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5431 LNCS, pp. 71-82, 3rd International Workshop on Algorithms and Computation, WALCOM 2009, Kolkata, India, 09/2/18. https://doi.org/10.1007/978-3-642-00202-1_7

Bae SW, Korman M, Tokuyama T. All farthest neighbors in the presence of highways and obstacles. In WALCOM: Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings. 2009. p. 71-82. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-00202-1_7

@inproceedings{1228daadcaef4881bf94d7b162884c7c,

title = "All farthest neighbors in the presence of highways and obstacles",

abstract = "We consider the problem of computing all farthest neighbors (and the diameter) of a given set of n points in the presence of highways and obstacles in the plane. When traveling on the plane, travelers may use highways for faster movement and must avoid all obstacles. We present an efficient solution to this problem based on knowledge from earlier research on shortest path computation. Our algorithms run in O(nm(logm + log2 n)) time using O(m + n) space, where the m is the combinatorial complexity of the environment consisting of highways and obstacles.",

author = "Bae, {Sang Won} and Matias Korman and Takeshi Tokuyama",

note = "Funding Information: Work by S.W. Bae was supported by the Brain Korea 21 Project. Work by M. Korman was supported by MEXT scolarship and CERIES GCOE project, MEXT Japan.; 3rd International Workshop on Algorithms and Computation, WALCOM 2009 ; Conference date: 18-02-2009 Through 20-02-2009",

year = "2009",

doi = "10.1007/978-3-642-00202-1_7",

language = "English",

isbn = "3642002013",

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

pages = "71--82",

booktitle = "WALCOM",

}

TY - GEN

T1 - All farthest neighbors in the presence of highways and obstacles

AU - Bae, Sang Won

AU - Korman, Matias

AU - Tokuyama, Takeshi

N1 - Funding Information: Work by S.W. Bae was supported by the Brain Korea 21 Project. Work by M. Korman was supported by MEXT scolarship and CERIES GCOE project, MEXT Japan.

PY - 2009

Y1 - 2009

N2 - We consider the problem of computing all farthest neighbors (and the diameter) of a given set of n points in the presence of highways and obstacles in the plane. When traveling on the plane, travelers may use highways for faster movement and must avoid all obstacles. We present an efficient solution to this problem based on knowledge from earlier research on shortest path computation. Our algorithms run in O(nm(logm + log2 n)) time using O(m + n) space, where the m is the combinatorial complexity of the environment consisting of highways and obstacles.

AB - We consider the problem of computing all farthest neighbors (and the diameter) of a given set of n points in the presence of highways and obstacles in the plane. When traveling on the plane, travelers may use highways for faster movement and must avoid all obstacles. We present an efficient solution to this problem based on knowledge from earlier research on shortest path computation. Our algorithms run in O(nm(logm + log2 n)) time using O(m + n) space, where the m is the combinatorial complexity of the environment consisting of highways and obstacles.

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

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

U2 - 10.1007/978-3-642-00202-1_7

DO - 10.1007/978-3-642-00202-1_7

M3 - Conference contribution

AN - SCOPUS:67650503955

SN - 3642002013

SN - 9783642002014

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

SP - 71

EP - 82

BT - WALCOM

T2 - 3rd International Workshop on Algorithms and Computation, WALCOM 2009

Y2 - 18 February 2009 through 20 February 2009

ER -

All farthest neighbors in the presence of highways and obstacles

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this