| 1. |
- Ebbers-Baumann, A, et al.
(author)
-
A fast algorithm for approximating the detour of a polygonal chain
- 2004
-
In: Computational Geometry. - 0925-7721. ; 27:2, s. 123-134
-
Journal article (peer-reviewed)abstract
- Let C be a simple(1) polygonal chain of n edges in the plane, and let p and q be two arbitrary points on C. The detour of C on (p, q) is defined to be the length of the subchain of C that connects p with q, divided by the Euclidean distance between p and q. Given an epsilon >0, we compute in time O((1)/(epsilon) n log n) a pair of points on which the chain makes a detour at least 1/(1 + epsilon) times the maximum detour. (C) 2003 Elsevier B.V. All rights reserved.
|
|
| 2. |
- Gudmundsson, J, et al.
(author)
-
Higher order Delaunay triangulations
- 2002
-
In: Computational Geometry. - 0925-7721. ; 23:1, s. 85-98
-
Journal article (peer-reviewed)abstract
- For a set P of points in the plane, we introduce a class of triangulations that is an extension of the Delaunay triangulation. Instead of requiring that for each triangle the circle through its vertices contains no points of P inside, we require that at most k points are inside the circle. Since there are many different higher-order Delaunay triangulations for a point set, other useful criteria for triangulations can be incorporated without sacrificing the well-shapedness too much. Applications include realistic terrain modeling and mesh generation. (C) 2002 Elsevier Science B.V. All rights reserved.
|
|
| 3. |
- Hammar, Mikael, et al.
(author)
-
Parallel Searching on m Rays
- 2001
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 18:3, s. 125-139
-
Journal article (peer-reviewed)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.
|
|
| 4. |
- Aichholzer, Oswin, et al.
(author)
-
Folding Polyominoes with Holes into a Cube
- 2021
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 93
-
Journal article (peer-reviewed)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.
|
|
| 5. |
- Andersson, Mattias, et al.
(author)
-
Approximate distance oracles for graphs with dense clusters
- 2007
-
In: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 37:3, s. 142-154
-
Journal article (peer-reviewed)abstract
- Let H1=(V,E1) be a collection of N pairwise vertex disjoint O(1)-spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let H2=(V,E2) be the graph on V with M edges of non-negative weight. The union of the two graphs is denoted G=(V,E1 u E2). We present a data structure of size O(M^2 + nlogn) that answers (1+ε)-approximate shortest path queries in G in constant time, where ε>0 is constant.
|
|
| 6. |
- Andersson, Mattias, et al.
(author)
-
Chips on wafers, or packing rectangles into grids
- 2005
-
In: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 30:2, s. 95-111
-
Journal article (peer-reviewed)abstract
- A set of rectangles S is said to be gridpacked if there exists a rectangular grid (not necessarily regular) such that every rectangle lies in the grid and there is at most one rectangle of S in each cell. The area of a grid packing is the area of a minimal bounding box that contains all the rectangles in the grid packing. We present an approximation algorithm that given a set S of rectangles and a real epsilon constant epsilon > 0 produces a grid packing of S whose area is at most (1 + epsilon) times larger than an optimal grid packing in polynomial time. If epsilon is chosen large enough the running time of the algorithm will be linear. We also study several interesting variants, for example the smallest area grid packing containing at least k less than or equal to n rectangles, and given a region A grid pack as many rectangles as possible within A Apart from the approximation algorithms we present several hardness results.
|
|
| 7. |
- Angelini, P., et al.
(author)
-
On the area requirements of Euclidean minimum spanning trees
- 2014
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 47:2, s. 200-213
-
Journal article (peer-reviewed)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.
|
|
| 8. |
- Arkin, Esther M, et al.
(author)
-
Convex transversals
- 2014
-
In: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 47:2, s. 224-239
-
Journal article (peer-reviewed)abstract
- We answer the question initially posed by Arik Tamir at the Fourth NYU Computational Geometry Day (March, 1987): “Given a collection of compact sets, can one decide in polynomial time whether there exists a convex body whose boundary intersects every set in the collection?”We prove that when the sets are segments in the plane, deciding existence of the convex stabber is NP-hard. The problem remains NP-hard if the sets are regular polygons. We also show that in 3D the stabbing problem is hard when the sets are balls. On the positive side, we give a polynomial-time algorithm to find a convex transversal of a maximum number of pairwise-disjoint segments in 2D if the vertices of the transversal are restricted to a given set of points. Our algorithm also finds a convex stabber of the maximum number of a set of convex pseudodisks in the plane.The stabbing problem is related to “convexity” of point sets measured as the minimum distance by which the points must be shifted in order to arrive in convex position; we give a PTAS to find the minimum shift in 2D, and a 2-approximation in any dimension. We also consider stabbing with vertices of a regular polygon – a problem closely related to approximate symmetry detection.
|
|
| 9. |
- Bae, Sang Won, et al.
(author)
-
Shortcuts for the circle
- 2019
-
In: Computational Geometry: Theory and Applications. - : Elsevier BV. - 0925-7721. ; 79, s. 37-54
-
Journal article (peer-reviewed)abstract
- Let C be the unit circle in R2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k⩾1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1⩽k⩽7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2+Θ(1/k[Formula presented]) for any k.
|
|
| 10. |
- Benkert, M., et al.
(author)
-
The Minimum Manhattan Network Problem : Approximations and Exact Solutions
- 2006
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 35:3, s. 188-208
-
Journal article (peer-reviewed)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.
|
|
