Academic Journal
Memory-Constrained Algorithms for Simple Polygons ∗
| العنوان: | Memory-Constrained Algorithms for Simple Polygons ∗ |
|---|---|
| المؤلفون: | Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, André Schulz |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://www.inf.fu-berlin.de/%7Erote/Papers/pdf/Memory-constrained%2Balgorithms%2Bfor%2Bsimple%2Bpolygons.pdf. |
| سنة النشر: | 2012 |
| المجموعة: | CiteSeerX |
| الوصف: | 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. 1 |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.303.9209; http://www.inf.fu-berlin.de/%7Erote/Papers/pdf/Memory-constrained%2Balgorithms%2Bfor%2Bsimple%2Bpolygons.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.303.9209 http://www.inf.fu-berlin.de/%7Erote/Papers/pdf/Memory-constrained%2Balgorithms%2Bfor%2Bsimple%2Bpolygons.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.A00FBEEB |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |