| 1. |
- Bose, Prosenjit, et al.
(författare)
-
Online routing in convex subdivisions
- 2000
-
Ingår i: Algorithms and Computation. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 3540412557 ; , s. 47-59
-
Konferensbidrag (refereegranskat)abstract
- We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation.
|
|
| 2. |
- Bose, Prosenjit, et al.
(författare)
-
Online routing in convex subdivisions
- 2002
-
Ingår i: International journal of computational geometry and applications. - 0218-1959. ; 12:4, s. 283-295
-
Tidskriftsartikel (refereegranskat)abstract
- We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation.
|
|
| 3. |
- Brodnik, Andrej, et al.
(författare)
-
Resizable arrays in optimal time and space
- 1999
-
Ingår i: Algorithms and Data Structures. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 3540662790 ; , s. 37-48
-
Konferensbidrag (refereegranskat)abstract
- We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l..l + n - 1], of fixed-size elements, as elements are added to or removed from one or both ends. Our structures also support access to the element in position i. All operations are performed in constant time. The extra space (i.e., the space used past storing the n current elements) is O(√n) at any point in time. This is shown to be within a constant factor of optimal, even if there are no constraints on the time. If desired, each memory block can be made to have size 2k - c for a specified constant c, and hence the scheme works effectively with the buddy system. The data structures can be used to solve a variety of problems with optimal bounds on time and extra storage. These include stacks, queues, randomized queues, priority queues, and deques.
|
|
| 4. |
- Burke, Kyle, et al.
(författare)
-
Single-Player and Two-Player Buttons & Scissors Games
- 2016
-
Ingår i: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015. - Cham : SPRINGER INT PUBLISHING AG. - 9783319485324 - 9783319485317 ; , s. 60-72
-
Konferensbidrag (refereegranskat)abstract
- We study the computational complexity of the Buttons amp; Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C = 2 colors but polytime solvable for C = 1. Similarly the game is NP-complete if every color is used by at most F = 4 buttons but polytime solvable for F amp;lt;= 3. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.
|
|
| 5. |
- Demaine, Erik D., et al.
(författare)
-
Rectangular Spiral Galaxies are still hard
- 2023
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 110
-
Tidskriftsartikel (refereegranskat)abstract
- Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called centers, the goal is to partition the grid into polyominoes such that each polyomino contains exactly one center and is 180 degrees rotationally symmetric about its center. We show that this puzzle is NP-complete, ASP-complete, and #P-complete even if (a) all solutions to the puzzle have rectangles for polyominoes; or (b) the polyominoes are required to be rectangles and all solutions to the puzzle have just 1 x 1, 1 x 3, and 3 x 1 rectangles. The proof for the latter variant also implies NP/ASP/#P-completeness of finding a noncrossing perfect matching in distance-2 grid graphs where edges connect vertices of Euclidean distance 2. Moreover, we prove NP-completeness of the design problem of minimizing the number of centers such that there exists a set of galaxies that exactly cover a given shape.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
|
|
