| 1. |
- Aichholzer, Oswin, et al.
(författare)
-
Folding Polyominoes into (Poly)Cubes
-
Ingår i: International journal of computational geometry and applications. - 0218-1959.
-
Tidskriftsartikel (refereegranskat)
|
|
| 2. |
|
|
| 3. |
- Aichholzer, Oswin, et al.
(författare)
-
Folding Polyominoes with Holes into a Cube
- 2021
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 93
-
Tidskriftsartikel (refereegranskat)abstract
- When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.
|
|
| 4. |
- Alt, Helmut, et al.
(författare)
-
Scandinavian Thins on Top of Cake : New and Improved Algorithms for Stacking and Packing
- 2014
-
Ingår i: Theory of Computing Systems. - : Springer Science and Business Media LLC. - 1432-4350 .- 1433-0490. ; 54:4, s. 689-714
-
Tidskriftsartikel (refereegranskat)abstract
- We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons.
|
|
| 5. |
- 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.
|
|
| 6. |
- Fekete, Sandor P., et al.
(författare)
-
Computing Nonsimple Polygons of Minimum Perimeter
- 2016
-
Ingår i: EXPERIMENTAL ALGORITHMS, SEA 2016. - Cham : SPRINGER INT PUBLISHING AG. - 9783319388502 - 9783319388519 ; , s. 134-149
-
Konferensbidrag (refereegranskat)abstract
- We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of integer programming, an additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting additional geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.
|
|
| 7. |
- Fekete, Sándor P., et al.
(författare)
-
Computing Nonsimple Polygons of Minimum Perimeter
- 2017
-
Ingår i: Journal of Computational Geometry. - Ottawa, Canada : Carleton University * Department of Mathematics and Statistics. - 1920-180X. ; 8:1
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the Minimum Perimeter Polygon Problem (MP3): for a given set V of points in the plane, find a polygon P with holes that has vertex set V , such that the total boundary length is smallest possible. The MP3 can be considered a natural geometric generalization of the Traveling Salesman Problem (TSP), which asks for a simple polygon with minimum perimeter. Just like the TSP, the MP3 occurs naturally in the context of curve reconstruction. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MP3. On the positive side, we provide constant-factor approximation algorithms. In addition to algorithms with theoretical worst-case guarantess, we provide practical methods for computing provably optimal solutions for relatively large instances, based on integer programming. An additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that restricting the set of connections between points to edges of the Delaunay triangulation yields results that are on average within 0.5% of the optimum for large classes of benchmark instances.
|
|
| 8. |
- Kostitsyna, Irina, et al.
(författare)
-
Most vital segment barriers
- 2019
-
Ingår i: Workshop on Algorithms and Data Structures. - : Springer, Cham. ; , s. 495-509
-
Konferensbidrag (refereegranskat)
|
|
| 9. |
- Kostitsyna, Irina, et al.
(författare)
-
On Minimizing Crossings in Storyline Visualizations
- 2015
-
Ingår i: GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2015. - Cham : SPRINGER INT PUBLISHING AG. - 9783319272610 - 9783319272603 ; , s. 192-198
-
Konferensbidrag (refereegranskat)abstract
- In a storyline visualization, we visualize a collection of interacting characters (e. g., in a movie, play, etc.) by x-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with n characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with O(n log n) crossings. Furthermore, we show that there exist storylines in this restricted case that require Omega(n log n) crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixedparameter tractable, when parameterized on the number of characters k. Our algorithm runs in time O(k!(2) k log k+ k!(2) m), where m is the number of meetings.
|
|
| 10. |
- Kostitsyna, Irina, et al.
(författare)
-
Optimizing airspace closure with respect to politicians egos
- 2015
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 586, s. 161-175
-
Tidskriftsartikel (refereegranskat)abstract
- When a president is landing at a busy airport, the airspace around the airport closes for commercial traffic. We show how to schedule the presidential squadron so as to minimize its impact on scheduled civilian flights; to obtain an efficient solution we use a "rainbow" algorithm recoloring aircraft on the fly as they are stored in a special type of forest. We also give a data structure to answer the following query efficiently: Given the presidents ego (the requested duration of airspace closure), when would be the optimal time to close the airspace? Finally, we study the dual problem: Given the time when the airspace closure must start, what is the longest ego that can be tolerated without sacrificing the general traffic? We solve the problem by drawing a Christmas tree in a delay diagram; the tree allows one to solve also the query version of the problem. (C) 2015 Elsevier B.V. All rights reserved.
|
|
| 11. |
|
|
