| 1. |
- Andersson, Mattias, et al.
(författare)
-
Approximate distance oracles for graphs with dense clusters
- 2004
-
Ingår i: Algorithms and Computation / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 3341, s. 53-64
-
Konferensbidrag (refereegranskat)abstract
- Let H-1 = (V, F-1) 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 H-2 = (V, F-2) be a graph on V with M edges of non-negative weight. The union of the two graphs is denoted G = (V, F-1 boolean OR F-2). We present a data structure of size O(M-2 + V log V) that answers (1 + epsilon)-approximate shortest path queries in G in constant time, where epsilon > 0 is constant.
|
|
| 2. |
- Andersson, Mattias, et al.
(författare)
-
Approximate distance oracles for graphs with dense clusters
- 2007
-
Ingår i: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 37:3, s. 142-154
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 3. |
- Andersson, Mattias, et al.
(författare)
-
Balanced partition of minimum spanning trees
- 2003
-
Ingår i: International Journal of Computational Geometry and Applications. - 0218-1959. ; 13:4, s. 303-316
-
Tidskriftsartikel (refereegranskat)abstract
- To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve dividing a task into a number of smaller tasks, while optimizing a specific objective function. In this paper we consider the problem of partitioning a given set S of n points in the plane into k subsets, S-1,...,S-k, such that max(1less than or equal toiless than or equal tok) MST(S-i) is minimized. Variants of this problem arise in applications from the shipbuilding industry. We show that this problem is NP-hard, and we also present an approximation algorithm for the problem, in the case when k is a fixed constant. The approximation algorithm runs in time O(n logn) and produces a partition that is within a factor (4/3 + epsilon) of the optimal if k = 2, and a factor (2 + epsilon) otherwise.
|
|
| 4. |
- Andersson, Mattias, et al.
(författare)
-
Balanced Partition of Minimum Spanning Trees
- 2002
-
Ingår i: Computational Science — ICCS 2002 / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 2331, s. 26-35
-
Konferensbidrag (refereegranskat)abstract
- To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve "optimally" dividing a task into k smaller tasks. We consider the problem of partitioning a given set S of n points (in the plane) into k subsets, S1,...,Sk that max 1leqslant i leqslant k |MST(Si) | is minimized. A variant of this problem arises in the shipbuilding industry [2].
|
|
| 5. |
- Andersson, Mattias, et al.
(författare)
-
Chips on wafers
- 2003
-
Ingår i: Algorithms and data structures. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540405450 ; 2748, s. 412-423
-
Konferensbidrag (refereegranskat)abstract
- A set of rectangles S is said to be grid packed 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 constant epsilon > 0 produces a grid packing of S whose area is at most (I + epsilon) times larger than an optimal 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.
|
|
| 6. |
- Andersson, Mattias, et al.
(författare)
-
Chips on wafers, or packing rectangles into grids
- 2005
-
Ingår i: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 30:2, s. 95-111
-
Tidskriftsartikel (refereegranskat)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. |
|
|
| 8. |
- Andersson, Mattias, et al.
(författare)
-
Restricted mesh simplification using edge contractions
- 2009
-
Ingår i: International Journal of Computational Geometry and Applications. - 0218-1959. ; 19:3, s. 247-265
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of simplifying a planar triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made on to one of its adjacent vertices, which results in removing the other adjacent vertex. We show that if the perimeter of the mesh consists of at most five vertices, then we can always find a vertex not on the perimeter which can be removed in this way. If the perimeter consists of more than five vertices such a vertex may not exist. In order to maintain a higher number of removable vertices under the above restriction, we study edge flips which can be performed in a visually smooth way. A removal of a vertex which is preceded by one such smooth operation is called a 2-step removal. Moreover, we introduce the possibility that the user defines "important" vertices (or edges) which have to remain intact. Given m such important vertices, or edges, we show that a simplification hierarchy of size O(n) and depth O(log(n/m))can be constructed by 2-step removals in O(n) time, such that the simplified graph contains the m important vertices and edges, and at most O(m) other vertices from the input graph. In some triangulations, many vertices may not even be 2-step removable. In order to provide the option to remove such vertices, we also define and examine k-step removals. This increases the lower bound on the number of removable vertices.
|
|
| 9. |
- Andersson, Mattias, et al.
(författare)
-
Restricted mesh simplification using edge contractions
- 2006
-
Ingår i: Computing and combinatorics / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540369257 ; 4112, s. 196-204
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of simplifying a triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made onto one of its adjacent vertices. In order to maintain a high number of contractible edges under this restriction, a small modification of the mesh around the edge to be contracted is allowed. Such a contraction is denoted a 2-step contraction. Given m "important" points or edges it is shown that a simplification hierarchy of size O(n) and depth O(log(n/m)) may be constructed in O(n) time. Further, for many edges not even 2-step contractions may be enough, and thus, the concept is generalized to k-step contractions.
|
|
| 10. |
- Ashvinkumar, Vikrant, et al.
(författare)
-
Local Routing in Sparse and Lightweight Geometric Graphs
- 2019
-
Ingår i: LIPICS. - : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. ; 149, s. 1-30
-
Konferensbidrag (refereegranskat)abstract
- Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.
|
|
