ORCID Profile
0000-0003-0983-7862
Current Organisations
Lunds Universitet
,
Lund University
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2017
Publisher: Elsevier BV
Date: 02-2005
Publisher: Association for Computing Machinery (ACM)
Date: 03-2008
Abstract: Given an arbitrary real constant ε 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 + ε)-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 + ε)-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 + ε)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = ω( n ) edges. The resulting data structure can be constructed in O ( m + n log n ) time using O ( n log n ) space.
Publisher: Elsevier BV
Date: 09-2005
Publisher: Springer Berlin Heidelberg
Date: 1999
Publisher: Elsevier BV
Date: 02-2002
Publisher: Springer Science and Business Media LLC
Date: 1999
Publisher: Society for Industrial & Applied Mathematics (SIAM)
Date: 2002
Publisher: Elsevier BV
Date: 10-2007
Publisher: Springer Science and Business Media LLC
Date: 25-01-2022
DOI: 10.1007/S00453-022-00930-2
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 $$\\varOmega (n)$$ Ω ( 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.
Publisher: Elsevier BV
Date: 08-2014
Publisher: Elsevier BV
Date: 08-2007
Publisher: World Scientific Pub Co Pte Lt
Date: 06-2009
DOI: 10.1142/S0218195909002940
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 onto 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.
Publisher: Springer Berlin Heidelberg
Date: 1997
DOI: 10.1007/BFB0036193
Publisher: World Scientific Pub Co Pte Lt
Date: 08-2003
DOI: 10.1142/S0218195903001190
Abstract: To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve iding 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 [Formula: see text] of n points in the plane into k subsets, [Formula: see text], such that [Formula: see text] 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 log n) and produces a partition that is within a factor (4/3+ε) of the optimal if k=2, and a factor (2+ε) otherwise.
No related grants have been discovered for Christos Levcopoulos.