Approximate shortest homotopic paths in weighted regions

Siu Wing Cheng; Jiongxin Jin; Antoine Vigneron; Yajun Wang

doi:10.1007/978-3-642-17514-5_10

Approximate shortest homotopic paths in weighted regions

Siu Wing Cheng^*, Jiongxin Jin, Antoine Vigneron, Yajun Wang

^*Corresponding author for this work

Computer, Electrical and Mathematical Sciences and Engineering

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

2 Scopus citations

Abstract

Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h ³/ε² kn polylog(k, n, 1/ε)), where k is the number of segments in P and h and n are the numbers of obstacles and vertices in T, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight.

Original language	English (US)
Title of host publication	Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages	109-120
Number of pages	12
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-17514-5_10
State	Published - 2010
Event	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: Dec 15 2010 → Dec 17 2010

Publication series

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

Other

Other	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Country/Territory	Korea, Republic of
City	Jeju Island
Period	12/15/10 → 12/17/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-17514-5_10

Cite this

Cheng, S. W., Jin, J., Vigneron, A., & Wang, Y. (2010). Approximate shortest homotopic paths in weighted regions. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 2 ed., pp. 109-120). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17514-5_10

Cheng, Siu Wing ; Jin, Jiongxin ; Vigneron, Antoine et al. / Approximate shortest homotopic paths in weighted regions. Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. pp. 109-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{cf5de6e2f4954f2983761ece3c225d5c,

title = "Approximate shortest homotopic paths in weighted regions",

abstract = "Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h 3/ε2 kn polylog(k, n, 1/ε)), where k is the number of segments in P and h and n are the numbers of obstacles and vertices in T, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight.",

author = "Cheng, {Siu Wing} and Jiongxin Jin and Antoine Vigneron and Yajun Wang",

note = "Funding Information: The research of Cheng and Jin was supported by the Research Grant Council, Hong Kong, China (project no. 612107).; 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

year = "2010",

doi = "10.1007/978-3-642-17514-5_10",

language = "English (US)",

isbn = "3642175163",

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

number = "PART 2",

pages = "109--120",

booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",

edition = "PART 2",

}

Cheng, SW, Jin, J, Vigneron, A & Wang, Y 2010, Approximate shortest homotopic paths in weighted regions. in Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6507 LNCS, pp. 109-120, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 12/15/10. https://doi.org/10.1007/978-3-642-17514-5_10

Approximate shortest homotopic paths in weighted regions. / Cheng, Siu Wing; Jin, Jiongxin; Vigneron, Antoine et al.
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. p. 109-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2).

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

TY - GEN

T1 - Approximate shortest homotopic paths in weighted regions

AU - Cheng, Siu Wing

AU - Jin, Jiongxin

AU - Vigneron, Antoine

AU - Wang, Yajun

N1 - Funding Information: The research of Cheng and Jin was supported by the Research Grant Council, Hong Kong, China (project no. 612107).

PY - 2010

Y1 - 2010

N2 - Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h 3/ε2 kn polylog(k, n, 1/ε)), where k is the number of segments in P and h and n are the numbers of obstacles and vertices in T, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight.

AB - Let P be a path between two points s and t in a polygonal subdivision T with obstacles and weighted regions. Given a relative error tolerance ε ∈(0,1), we present the first algorithm to compute a path between s and t that can be deformed to P without passing over any obstacle and the path cost is within a factor 1 + ε of the optimum. The running time is O(h 3/ε2 kn polylog(k, n, 1/ε)), where k is the number of segments in P and h and n are the numbers of obstacles and vertices in T, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight.

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

U2 - 10.1007/978-3-642-17514-5_10

DO - 10.1007/978-3-642-17514-5_10

M3 - Conference contribution

AN - SCOPUS:78650858803

SN - 3642175163

SN - 9783642175169

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

SP - 109

EP - 120

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

Cheng SW, Jin J, Vigneron A, Wang Y. Approximate shortest homotopic paths in weighted regions. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 ed. 2010. p. 109-120. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-17514-5_10

Approximate shortest homotopic paths in weighted regions

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this