| 1. |
- 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.
|
|
| 2. |
- 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].
|
|
| 3. |
|
|
| 4. |
- Andersson, Mattias, et al.
(författare)
-
Reporting leaders and followers among trajectories of moving point objects
- 2008
-
Ingår i: GeoInformatica. - : Springer Science and Business Media LLC. - 1384-6175 .- 1573-7624. ; 12:4, s. 497-528
-
Tidskriftsartikel (refereegranskat)abstract
- Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects, opening new options for a better understanding of the processes involved. In this paper we investigate spatio-temporal movement patterns in large tracking data sets. We present a natural definition of the pattern 'one object is leading others', which is based on behavioural patterns discussed in the behavioural ecology literature. Such leadership patterns can be characterised by a minimum time length for which they have to exist and by a minimum number of entities involved in the pattern. Furthermore, we distinguish two models (discrete and continuous) of the time axis for which patterns can start and end. For all variants of these leadership patterns, we describe algorithms for their detection, given the trajectories of a group of moving entities. A theoretical analysis as well as experiments show that these algorithms efficiently report leadership patterns.
|
|
| 5. |
- Andersson, Mattias, et al.
(författare)
-
Reporting leadership patterns among trajectories
- 2007
-
Ingår i: Proceedings of the 2007 ACM symposium on Applied computing. - New York, NY, USA : ACM. - 1595934804 ; , s. 3-7
-
Konferensbidrag (refereegranskat)abstract
- Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects, opening new options for a better understanding of the processes involved. In this paper we investigate spatio-temporal movement patterns in large tracking data sets. We present a natural definition of the pattern 'one object is leading others', and discuss how such leadership patterns can be computed from a group of moving entities. The proposed definition is based on behavioural patterns discussed in the behavioural ecology literature. We also present several algorithms for computing the pattern, and they are analysed both theoretically and experimentally.
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- Ashvinkumar, Vikrant, et al.
(författare)
-
Local Routing in Sparse and Lightweight Geometric Graphs
- 2022
-
Ingår i: Algorithmica. - : Springer. - 0178-4617 .- 1432-0541. ; 84, s. 1316-1340
-
Tidskriftsartikel (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 (SIAM J Comput 33(4):937-951, 2004) 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.
|
|
| 10. |
- Bae, Sang Won, et al.
(författare)
-
Shortcuts for the circle
- 2017
-
Ingår i: 28th International Symposium on Algorithms and Computation, ISAAC 2017. - 9783959770545 ; 92, s. 1-13
-
Konferensbidrag (refereegranskat)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 2 3 ) for any k.
|
|
| 11. |
- Bae, Sang Won, et al.
(författare)
-
Shortcuts for the circle
- 2019
-
Ingår i: Computational Geometry: Theory and Applications. - : Elsevier BV. - 0925-7721. ; 79, s. 37-54
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 12. |
- Bergenzaun, Lill, et al.
(författare)
-
Assessing left ventricular systolic function in shock : evaluation of echocardiographic parameters in intensive care
- 2011
-
Ingår i: Critical Care. - : BioMed Central. - 1364-8535 .- 1466-609X. ; 15:4
-
Tidskriftsartikel (refereegranskat)abstract
- INTRODUCTION: Assessing left ventricular (LV) systolic function in a rapid and reliable way can be challenging in the critically ill patient. The purpose of this study was to evaluate the feasibility and reliability of, as well as the association between, commonly used LV systolic parameters, by using serial transthoracic echocardiography (TTE). METHODS: Fifty patients with shock and mechanical ventilation were included. TTE examinations were performed daily for a total of 7 days. Methods used to assess LV systolic function were visually estimated, "eyeball" ejection fraction (EBEF), the Simpson single-plane method, mean atrioventricular plane displacement (AVPDm), septal tissue velocity imaging (TDIs), and velocity time integral in the left ventricular outflow tract (VTI). RESULTS: EBEF, AVPDm, TDIs, VTI, and the Simpson were obtained in 100%, 100%, 99%, 95% and 93%, respectively, of all possible examinations. The correlations between the Simpson and EBEF showed r values for all 7 days ranging from 0.79 to 0.95 (P < 0.01). the Simpson correlations with the other LV parameters showed substantial variation over time, with the poorest results seen for TDIs and AVPDm. The repeatability was best for VTI (interobserver coefficient of variation (CV) 4.8%, and intraobserver CV, 3.1%), and AVPDm (5.3% and 4.4%, respectively), and worst for the Simpson method (8.2% and 10.6%, respectively). CONCLUSIONS: EBEF and AVPDm provided the best, and Simpson, the worst feasibility when assessing LV systolic function in a population of mechanically ventilated, hemodynamically unstable patients. Additionally, the Simpson showed the poorest repeatability. We suggest that EBEF can be used instead of single-plane Simpson when assessing LV ejection fraction in this category of patients. TDIs and AVPDm, as markers of longitudinal function of the LV, are not interchangeable with LV ejection fraction.
|
|
| 13. |
- Bergenzaun, Lill, et al.
(författare)
-
High-sensitive cardiac Troponin T is superior to echocardiography in predicting 1-year mortality in patients with SIRS and shock in intensive care.
- 2012
-
Ingår i: BMC Anesthesiology. - : BioMed Central. - 1471-2253 .- 1471-2253. ; 12:25
-
Tidskriftsartikel (refereegranskat)abstract
- BACKGROUND: Left ventricular (LV) dysfunction is well documented in the critically ill. We assessed 1-year mortality in relation to cardiac biomarkers and LV function parameters by echocardiography in patients with shock. METHODS: A prospective, observational, cohort study of 49 patients. B-natriuretic peptide (BNP), highsensitive troponin T (hsTNT) and transthoracic echocardiography (TTE) were assessed within 12 h of study inclusion. LV systolic function was measured by ejection fraction (LVEF), mean atrioventricular plane displacement (AVPDm), peak systolic tissue Doppler velocity imaging (TDIs) and velocity time integral in the LV outflow tract (LVOT VTI). LV diastolic function was evaluated by transmitral pulsed Doppler (E, A, E/A, E-deceleration time), tissue Doppler indices (e, a, E/e) and left atrial volume (La volume). APACHE II (Acute Physiology and Chronic Health Evaluation) and SOFA (Sequential Organ Failure Assessment) scores were calculated. RESULTS: hsTNT was significantly higher in non-survivors than in survivors (60 [17.0-99.5] vs 168 [89.8-358] ng/l, p = 0.003). Other univariate predictors of mortality were APACHE II (p = 0.009), E/e (p = 0.023), SOFA (p = 0.024) and age (p = 0.031). Survivors and nonsurvivors did not differ regarding BNP (p = 0.26) or any LV systolic function parameter (LVEF p = 0.87, AVPDm p = 0.087, TDIs p = 0.93, LVOT VTI p = 0.18). Multivariable logistic regression analysis identified hsTNT (p = 0.010) as the only independent predictor of 1-year mortality; adjusted odds ratio 2.0 (95% CI 1.2- 3.5). CONCLUSIONS: hsTNT was the only independent predictor of 1-year mortality in patients with shock. Neither BNP nor echocardiographic parameters had an independent prognostic value. Further studies are needed to establish the clinical significance of elevated hsTNT in patients in shock.
|
|
| 14. |
- de Berg, Mark, et al.
(författare)
-
TSP with neighborhoods of varying size
- 2002
-
Ingår i: Algorithms — ESA 2002 / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 2461, s. 187-199
-
Konferensbidrag (refereegranskat)abstract
- In TSP with neighborhoods we are given a set of objects in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the objects are of approximately the same size. We present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat objects of arbitrary size. We also show that the problem is APX-hard and cannot be approximated within a factor of 391/390 in polynomial time, unless P=NP.
|
|
| 15. |
- El Shawi, Radwa, et al.
(författare)
-
Quickest path queries on transportation network
- 2014
-
Ingår i: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 47:7, s. 695-709
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 16. |
- Guðmundsson, Arnar, 1990-
(författare)
-
Iron-Catalyzed Reactions and X-Ray Absorption Spectroscopic Studies of Palladium- and Ruthenium-Catalyzed Reactions
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The focus of this thesis is twofold: The first is on the application of iron catalysis for organic transformations. The second is on the use of in situ X-ray absorption spectroscopy (XAS) to investigate the mechanisms of a heterogeneous palladium-catalyzed reaction and a homogeneous ruthenium-catalyzed reaction.In chapters two, three and four, the use of iron catalyst VI, or its analog X, is described for (I) the DKR of sec-alcohols to produce enantiomerically pure acetates; (II) the cycloisomerization of α-allenols and α-allenic sulfonamides, giving 2,3-dihydrofuran or 2,3-dihydropyrrole products, respectively, with excellent diastereoselectivity; and (III) the aerobic biomimetic oxidation of primary- and secondary alcohols to their respective aldehydes or ketones.In the fifth chapter, XAS is used to elucidate the mechanisms of a Pd(II)-AmP-MCF-catalyzed lactonization reaction of acetylenic acids. The catalyst was known to deactivate during the reaction and the XAS studies identified the cause of this deactivation. A reactivation strategy was subsequently developed based on these findings.In the sixth and final chapter, XAS is used to examine the activation mechanism of a ruthenium racemization catalyst and a ruthenium-acyl intermediate which had previously been speculated to be formed in the activation process was confirmed.
|
|
| 17. |
- Gudmundsson, Joachim, et al.
(författare)
-
Approximate distance oracles for geometric graphs
- 2002
-
Ingår i: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. - 089871513X ; , s. 828-837
-
Konferensbidrag (refereegranskat)abstract
- Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+n log n) preprocessing, we present an approximation scheme to answer (1+ε)-approximate shortest path queries in O(1) time. The data structure uses O(n log n) space.
|
|
| 18. |
- Gudmundsson, Joachim, et al.
(författare)
-
Approximate distance oracles for geometric spanners
- 2008
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6333 .- 1549-6325. ; 4:1
-
Tidskriftsartikel (refereegranskat)abstract
- Given an arbitrary real constant epsilon > 0, and a geometric graph G in d-dimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1 + epsilon)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O( n log n) time using O( n log n) space. This represents the first data structure that answers (1 + epsilon)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with "rounded" obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + epsilon)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = omega(n) edges. The resulting data structure can be constructed in O(m + n log n) time using O(n log n) space.
|
|
| 19. |
- Gudmundsson, Joachim
(författare)
-
Geometric Decompositions and Networks - Approximation Bounds and Algorithms
- 2000
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis we focus on four problems in computational geometry: In the first four chapters we consider the problem of covering an arbitrary polygon with simpler polygons, i.e., rectangles. We present several approximation algorithms for this problem, and also some lower bounds on the number of rectangles needed in a covering of a hole-free polygon and on the time-complexity for this and related problems. Then, we consider a generalization of the well-known Euclidean traveling salesman problem (TSP), namely the TSP with neighborhoods problem. In the TSP with neighborhoods problem we are given a collection of polygonal regions, and we seek the shortest tour that visits each neighborhood at least once. We give approximation algorithms for the problem and also show a result on the hardness of the problem. Next we turn our attention to the problem of finding a t-spanner of a complete geometric graph. The aim is to produce a sparse graph with a small number of edges and with low total weight, that is almost as "good" as a complete graph. With good we mean that for every pair of points in the graph there exists a path in the spanner graph that is at most t times longer than the distance between the two points. We present several approximation algorithms for this problem. In the final chapter of the thesis we introduce the concept of higher-order Delaunay triangulations. We give an algorithm to compute which edges can be included in a higher-order Delaunay triangulation. We show that for 1-order Delaunay triangulations, most of the criteria we study can be optimized in O(n log n) time, for example, minimizing the number of local minima, the number of local extrema, the maximum angle, area triangle, and degree of any vertex.
|
|
| 20. |
- Gudmundsson, Joachim, et al.
(författare)
-
Minimum weight pseudo-triangulations
- 2004
-
Ingår i: FSTTCS 2004 / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. ; 3328, s. 299-310
-
Konferensbidrag (refereegranskat)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(nlogn)-time algorithm that produces a pseudo-triangulation of weight O(wt(M(S))logn) which is shown to be asymptotically worst-case optimal, i.e., there exists a point set S for which every pseudo-triangulation has weight Omega(wt(M(S))logn), where wt(M(S)) is the weight of a minimum 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.
|
|
| 21. |
- Gudmundsson, Joachim, et al.
(författare)
-
Minimum weight pseudo-triangulations
- 2007
-
Ingår i: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 38:3, s. 139-153
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 22. |
- Kowaluk, Miroslaw, et al.
(författare)
-
A path cover technique for LCAs in dags
- 2008
-
Ingår i: Algorithm theory – SWAT 2008 / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783540699002 ; 5124, s. 222-223
-
Konferensbidrag (refereegranskat)abstract
- As a second major result we show how to combine the path cover technique with LCA solutions for dags with small depth [9]. Our algorithm attains the best known upper time bound for this problem of O(n 2.575). However, most notably, the algorithm performs better on a vast amount of input dags, i.e. dags that do not have an almost linear-sized subdag of extremely regular structure. Finally, we apply our technique to improve the general upper time bounds on the worst case time complexity for the problem of reporting LCAs for each triple of vertices recently established by Yuster[26].
|
|
| 23. |
|
|
| 24. |
- Levcopoulos, Christos, et al.
(författare)
-
A fast approximation algorithm for TSP with neighborhoods and red-blue separation
- 1999
-
Ingår i: Computing and combinatorics / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. ; 1627, s. 473-482
-
Konferensbidrag (refereegranskat)abstract
- In TSP with neighborhoods (TSPN) we are given a collec-tion X of k polygonal regions, called neighborhoods, with totally n ver-tices, and we seek the shortest tour that visits each neighborhood. TheEuclidean TSP is a special case of the TSPN problem, so TSPN is alsoNP-hard. In this paper we present a simple and fast algorithm that, givena start point, computes a TSPN tour of length O(log k) times the opti-mum in time O(n+k log k). When no start point is given we show howto compute a good start point in time O(n2 log n), hence we obtain alogarithmic approximation algorithm that runs in time O(n2 log n). Wealso present an algorithm which performs at least one of the followingtwo tasks (which of these tasks is performed depends on the given input):(1) It outputs in time O(n log n) a TSPN tour of length O(log k) timesthe optimum. (2) It outputs a TSPN tour of length less than (1+) timesthe optimum in cubic time, where is an arbitrary real constant givenas an optional parameter.The results above are signicant improvements, since the best previouslyknown logarithmic approximation algorithm runs in (n5) time in theworst case.
|
|
| 25. |
|
|
| 26. |
- Levcopoulos, Christos, et al.
(författare)
-
Close Approximations of Minimum Rectangular Coverings
- 1999
-
Ingår i: Journal of Combinatorial Optimization. - 1382-6905. ; 3:4, s. 437-452
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of covering arbitrary polygons with rectangles. The rectangles must lie entirely within the polygon. (This requires that the interior angles of the polygon are all greater than or equal to 90 degrees.) We want to cover the polygon with as few rectangles as possible. This problem has an application in fabricating masks for integrated circuits. In this paper we will describe the first polynomial algorithm, guaranteeing an O(log n) approximation factor, provided that the n vertices of the input polygon are given as polynomially bounded integer coordinates. By the same technique we also obtain the first algorithm producing a covering which is within a constant factor of the optimal in exponential time (compared to the doubly-exponential known before).
|
|
| 27. |
- Levcopoulos, Christos, et al.
(författare)
-
Close approximations of minimum rectangular coverings
- 1996
-
Ingår i: Foundations of software technology and theoretical computer science : 16th Conference / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 3540620346 ; 1180, s. 135-146
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of covering arbitrary polygons with rectangles. The rectangles must lie entirely within the polygon. (This requires that the interior angles of the polygon are all greater than or equal to 90 degrees.) We want to cover the polygon with as few rectangles as possible. This problem has an application in fabricating masks for integrated circuits. In this paper we will describe the first polynomial algorithm, guaranteeing an O(log n) approximation factor, provided that the n vertices of the input polygon are given as polynomially bounded integer coordinates. By the same technique we also obtain the first algorithm producing a covering which is within a constant factor of the optimal in exponential time (compared to the doubly-exponential known before).
|
|
| 28. |
- Thybo, Hans, et al.
(författare)
-
ScanArray : A Broadband Seismological Experiment in the Baltic Shield
- 2021
-
Ingår i: Seismological Research Letters. - : Seismological Society of America (SSA). - 0895-0695 .- 1938-2057. ; 92:5, s. 2811-2823
-
Tidskriftsartikel (refereegranskat)abstract
- The ScanArray international collaborative program acquired broadband seismological data at 192 locations in the Baltic Shield during the period between 2012 and 2017. The main objective of the program is to provide seismological constraints on the structure of the lithospheric crust and mantle as well as the sublithospheric upper mantle. The new information will be applied to studies of how the lithospheric and deep structure affect observed fast topographic change and geological‐tectonic evolution of the region. The program also provides new information on local seismicity, focal mechanisms, and seismic noise. The recordings are generally of very high quality and are used for analysis by various seismological methods, including P‐ and S‐wave receiver functions for the crust and upper mantle, surface wave and ambient noise inversion for seismic velocity, body‐wave P‐ and S‐wave tomography for upper mantle velocity structure using ray and finite frequency methods, and shear‐wave splitting measurements for obtaining bulk anisotropy of the upper and lowermost mantle. Here, we provide a short overview of the data acquisition and initial analysis of the new data, together with an example of integrated seismological results obtained by the project group along a representative ∼1800‐km‐long profile across most of the tectonic provinces in the Baltic Shield between Denmark and the North Cape. The first models support a subdivision of the Paleoproterozoic Svecofennian province into three domains, where the highest topography of the Scandes mountain range in Norway along the Atlantic Coast has developed solely in the southern and northern domains, whereas the topography is more subdued in the central domain.
|
|
