| 1. |
- Hammar, Mikael, et al.
(författare)
-
Parallel Searching on m Rays
- 2001
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 18:3, s. 125-139
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate parallel searching on $m$ concurrent rays. We assume that a target $t$ is located somewhere on one of the rays; we are given a group of $m$ point robots each of which has to reach $t$. Furthermore, we assume that the robots have no way of communicating over distance. Given a strategy $S$ we are interested in the competitive ratio defined as the ratio of the time needed by the robots to reach $t$ using $S$ and the time needed to reach $t$ if the location of $t$ is known in advance. If a lower bound on the distance to the target is known, then there is a simple strategy which achieves a competitive ratio of~9 --- independent of $m$. We show that 9 is a lower bound on the competitive ratio for two large classes of strategies if $m\geq 2$. If the minimum distance to the target is not known in advance, we show a lower bound on the competitive ratio of $1 + 2 (k + 1)^{k + 1} / k^k$ where $k = \left\lceil\log m\right\rceil$ where $\log$ is used to denote the base 2 logarithm. We also give a strategy that obtains this ratio.
|
|
| 2. |
- 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.
|
|
| 3. |
- Angelini, P., et al.
(författare)
-
On the area requirements of Euclidean minimum spanning trees
- 2014
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 47:2, s. 200-213
-
Tidskriftsartikel (refereegranskat)abstract
- In their seminal paper on Euclidean minimum spanning trees, Monma and Suri (1992) proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; however, the authors conjectured that there exist n-vertex trees of maximum degree 5 that require c(n) x c(n) area to be embedded as Euclidean minimum spanning trees, for some constant c > 1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees.
|
|
| 4. |
- Benkert, M., et al.
(författare)
-
The Minimum Manhattan Network Problem : Approximations and Exact Solutions
- 2006
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 35:3, s. 188-208
-
Tidskriftsartikel (refereegranskat)abstract
- Given a set of points in the plane and a constant t⩾1, a Euclidean t-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most t. Such networks have applications in transportation or communication network design and have been studied extensively.In this paper we study 1-spanners under the Manhattan (or L1-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an x- and y-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e., Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set P of n points, our algorithm computes in O(nlogn) time and linear space a Manhattan network for P whose length is at most 3 times the length of an MMN of P.We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets.
|
|
| 5. |
- Cannon, Sarah, et al.
(författare)
-
Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
- 2018
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 68, s. 89-100
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a generalization of the classical Art Gallery Problem, where instead of a light source, the guards, called k-transmitters, model a wireless device with a signal that can pass through at most k walls. We show it is NP-hard to compute a minimum cover of point 2-transmitters, point k-transmitters, and edge 2-transmitters in a simple polygon. The point 2-transmitter result extends to orthogonal polygons. In addition, we give necessity and sufficiency results for the number of edge 2-transmitters in general, monotone, orthogonal monotone, and orthogonal polygons.
|
|
| 6. |
- Daescu, Ovidiu, et al.
(författare)
-
Altitude Terrain Guarding and Guarding Uni-Monotone Polygons
- 2019
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 84, s. 22-35
-
Tidskriftsartikel (refereegranskat)abstract
- We present an optimal, linear-time algorithm for the following version of terrain guarding: given a 1.5D terrain and a horizontal line, place the minimum number of guards on the line to see all of the terrain. We prove that the cardinality of the minimum guard set coincides with the cardinality of a maximum number of “witnesses”, i.e., terrain points, no two of which can be seen by a single guard. We show that our results also apply to the Art Gallery problem in “monotone mountains”, i.e., x-monotone polygons with a single edge as one of the boundary chains. This means that any monotone mountain is “perfect” (its guarding number is the same as its witness number); we thus establish the first non-trivial class of perfect polygons.
|
|
| 7. |
- 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/).
|
|
| 8. |
- Masood, Talha Bin, et al.
(författare)
-
Parallel computation of alpha complexes for biomolecules
- 2020
-
Ingår i: Computational geometry. - : ELSEVIER. - 0925-7721 .- 1879-081X. ; 90
-
Tidskriftsartikel (refereegranskat)abstract
- The alpha complex, a subset of the Delaunay triangulation, has been extensively used as the underlying representation for biomolecular structures. We propose a GPU-based parallel algorithm for the computation of the alpha complex, which exploits the knowledge of typical spatial distribution and sizes of atoms in a biomolecule. Unlike existing methods, this algorithm does not require prior construction of the Delaunay triangulation. The algorithm computes the alpha complex in two stages. The first stage proceeds in a bottom-up fashion and computes a superset of the edges, triangles, and tetrahedra belonging to the alpha complex. The false positives from this estimation stage are removed in a subsequent pruning stage to obtain the correct alpha complex. Computational experiments on several biomolecules demonstrate the superior performance of the algorithm, up to a factor of 50 when compared to existing methods that are optimized for biomolecules. (C) 2020 Elsevier B.V. All rights reserved.
|
|
| 9. |
- Mitchell, Joseph S. B., et al.
(författare)
-
Minimum-link paths revisited
- 2014
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 47:6, s. 651-667
-
Tidskriftsartikel (refereegranskat)abstract
- A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case (C = 2). We study exact and approximation algorithms for minimum-link C-oriented paths and paths with unrestricted orientations, both in C-oriented and in general domains. Our two main algorithms are as follows: A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains. An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm. We also obtain several related results: 3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain). An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones. An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain. A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path. A notion of "robust" paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1.
|
|
| 10. |
|
|
