講演抄録/キーワード |
講演名 |
2009-04-17 14:05
An Improved Algorithm for Inserting a Highway in a City Metric Based on Qua-siconvex Optimization ○Matias Korman・Takeshi Tokuyama(Tohoku Univ.) COMP2009-5 |
抄録 |
(和) |
(まだ登録されていません) |
(英) |
We introduce an improved algorithm to locate a segment highway such that the maximum city distance between a given set of $n$ points is minimized (where the city distance is measured with speed $v>1$ on a highway and 1 in the underlying metric elsewhere). We consider that such highway is built in a complex transportation system with $H$ other highways and obstacles. The algorithm runs in $O(n^3 H^3(\log^2 n + \log H))$ time using $O(nH)$ space improving the previous $O(n^4 H^4)$ time and space bound. |
キーワード |
(和) |
/ / / / / / / |
(英) |
Computational Geometry / Algorithms / City Metric / Shortest Paths / Quasiconvex Optimization / / / |
文献情報 |
信学技報, vol. 109, no. 9, COMP2009-5, pp. 29-35, 2009年4月. |
資料番号 |
COMP2009-5 |
発行日 |
2009-04-10 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-5 |