| 1. |
- 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.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- 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.
|
|
| 5. |
- Cannon, Sarah, et al.
(author)
-
Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
- 2018
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 68, s. 89-100
-
Journal article (peer-reviewed)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.
(author)
-
Altitude Terrain Guarding and Guarding Uni-Monotone Polygons
- 2019
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 84, s. 22-35
-
Journal article (peer-reviewed)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.
(author)
-
Rectangular Spiral Galaxies are still hard
- 2023
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 110
-
Journal article (peer-reviewed)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.
(author)
-
Parallel computation of alpha complexes for biomolecules
- 2020
-
In: Computational geometry. - : ELSEVIER. - 0925-7721 .- 1879-081X. ; 90
-
Journal article (peer-reviewed)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.
(author)
-
Minimum-link paths revisited
- 2014
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 47:6, s. 651-667
-
Journal article (peer-reviewed)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. |
|
|
| 11. |
- 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.
|
|
| 12. |
- 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.
|
|
| 13. |
- 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.
|
|
| 14. |
- 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.
|
|
| 15. |
- 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.
|
|
| 16. |
- 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.
|
|
| 17. |
- Bohler, Cecilia, et al.
(author)
-
Forest-like abstract Voronoi diagrams in linear time
- 2018
-
In: Computational Geometry: Theory and Applications. - : Elsevier BV. - 0925-7721. ; 68, s. 134-145
-
Journal article (peer-reviewed)abstract
- Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V(S) is a tree, and for each subset S'⊂S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V(S) inside D can be constructed in linear time.
|
|
| 18. |
- El Shawi, Radwa, et al.
(author)
-
Quickest path queries on transportation network
- 2014
-
In: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 47:7, s. 695-709
-
Journal article (peer-reviewed)abstract
- This paper considers the problem of finding the cost of a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We show how the transportation network with n edges in the Euclidean plane can be preprocessed in time O ((n/epsilon)(2) log n) into a data structure of size O ((n/epsilon)(2)) such that (1 + epsilon)-approximate quickest path cost queries between any two points in the plane can be answered in time O (1/epsilon(4) log n). In addition we consider the nearest neighbor problem in a transportation network: given a transportation network with n edges in the Euclidean plane together with a set Z of m sites, a query point q is an element of R-2, find the nearest site in Z from q. We show how the transportation network can be preprocessed in time O ((n(2) + nm) log (n + m)) such that (1 + epsilon)-nearest neighbor query can be answered in time O (1/epsilon(2) log(n + m)). (C) 2014 Published by Elsevier B.V.
|
|
| 19. |
- Gudmundsson, Joachim, et al.
(author)
-
Minimum weight pseudo-triangulations
- 2007
-
In: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 38:3, s. 139-153
-
Journal article (peer-reviewed)abstract
- We consider the problem of computing a minimum weight pseudo-triangulation of a set S of n points in the plane. We first present an O(n log n)-time algorithm that produces a pseudo-triangulation of weight O(log n - wt(M(S))) which is shown to be asymptotically worst-case optimal, i.e., there exists a point set S for which every pseudo-triangulation has weight 0 (log n - wt(M(S))), where wt(.M(S)) is the weight of a minimum weight spanning tree of S. We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon. (C) 2007 Elsevier B.V. All rights reserved.
|
|
| 20. |
|
|
| 21. |
- Omer, Hélène, et al.
(author)
-
Understanding the role of Propionibacterium acnes in acne vulgaris : The critical importance of skin sampling methodologies
- 2017
-
In: Clinics in Dermatology. - : Elsevier BV. - 0738-081X .- 1879-1131. ; 35:2, s. 118-129
-
Journal article (peer-reviewed)abstract
- Acne vulgaris is a chronic inflammatory skin condition classified by the Global Burden of Disease Study as the eighth most prevalent disease worldwide. The pathophysiology of the condition has been extensively studied, with an increase in sebum production, abnormal keratinization of the pilosebaceous follicle, and an inflammatory immune response all implicated in its etiology. One of the most disputed points, however, is the role of the gram:positive anaerobic bacterium Propionibacterium acnes in the development of acne, particularly when this organism is also found in normal sebaceous follicles of healthy skin. Against this background, we now describe the different sampling strategies that have been adopted for qualitative and quantitative study of P acnes within intact hair follicles of the skin and discuss the strengths and weaknesses of such methodologies for investigating the role of P acnes in the development of acne.
|
|
