論文

査読有り
2014年4月

Reprint of: Memory-constrained algorithms for simple polygons

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
  • Tetsuo Asano
  • ,
  • Kevin Buchin
  • ,
  • Maike Buchin
  • ,
  • Matias Korman
  • ,
  • Wolfgang Mulzer
  • ,
  • Guenter Rote
  • ,
  • Andre Schulz

47
3
開始ページ
469
終了ページ
479
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1016/j.comgeo.2013.11.004
出版者・発行元
ELSEVIER SCIENCE BV

A constant-work-space algorithm has read-only access to an input array and may use only O (1) additional words of O (log n) bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O (n(2)) time and constant workspace. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O (n(2)/s) time. (C) 2013 Elsevier B.V. All rights reserved.

Web of Science ® 被引用回数 : 6

リンク情報
DOI
https://doi.org/10.1016/j.comgeo.2013.11.004
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000330084600003&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/journals/comgeo/comgeo47.html#journals/comgeo/AsanoBBKMRS14
ID情報
  • DOI : 10.1016/j.comgeo.2013.11.004
  • ISSN : 0925-7721
  • eISSN : 1879-081X
  • DBLP ID : journals/comgeo/AsanoBBKMRS14
  • Web of Science ID : WOS:000330084600003

エクスポート
BibTeX RIS