Source author record

Christos Levcopoulos

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Local Routing in Sparse and Lightweight Geometric Graphs

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 [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is $O(1)$ -competitive. However, a Delaunay triangulation can have $Ω(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.

preprint2016arXiv

A Fire Fighter's Problem

Suppose that a circular fire spreads in the plane at unit speed. A single fire fighter can build a barrier at speed $v>1$ . How large must $v$ be to ensure that the fire can be contained, and how should the fire fighter proceed? We contribute two results. First, we analyze the natural curve $\mbox{FF}_v$ that develops when the fighter keeps building, at speed $v$ , a barrier along the boundary of the expanding fire. We prove that the behavior of this spiralling curve is governed by a complex function $(e^{w Z} - s \, Z)^{-1}$ , where $w$ and $s$ are real functions of $v$ . For $v>v_c=2.6144 \ldots$ all zeroes are complex conjugate pairs. If $ϕ$ denotes the complex argument of the conjugate pair nearest to the origin then, by residue calculus, the fire fighter needs $Θ( 1/ϕ)$ rounds before the fire is contained. As $v$ decreases towards $v_c$ these two zeroes merge into a real one, so that argument $ϕ$ goes to~0. Thus, curve $\mbox{FF}_v$ does not contain the fire if the fighter moves at speed $v=v_c$ . (That speed $v>v_c$ is sufficient for containing the fire has been proposed before by Bressan et al. [7], who constructed a sequence of logarithmic spiral segments that stay strictly away from the fire.) Second, we show that any curve that visits the four coordinate half-axes in cyclic order, and in inreasing distances from the origin, needs speed $v>1.618\ldots$ , the golden ratio, in order to contain the fire. Keywords: Motion Planning, Dynamic Environments, Spiralling strategies, Lower and upper bounds

preprint2016arXiv

Efficiently Correcting Matrix Products

We study the problem of efficiently correcting an erroneous product of two $n\times n$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most $k$ erroneous entries running in $\tilde{O}(n^2+kn)$ time and a deterministic $\tilde{O}(kn^2)$ -time algorithm for this problem (where the notation $\tilde{O}$ suppresses polylogarithmic terms in $n$ and $k$ ).

preprint2011arXiv

Quickest Path Queries on Transportation Network

This paper considers the problem of finding 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 traveller may enter and exit the network at any point on the roads. Along any road the traveller moves with a fixed speed depending on the road, and outside the network the traveller moves at unit speed in any direction. We give an exact algorithm for the basic version of the problem: given a transportation network of total complexity n in the Euclidean plane, a source point s and a destination point t, and the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n^2 log n) into a data structure of size O(n^2) such that (1 + ε)-approximate cheapest path cost queries between any two points in the plane can be answered in time O(1ε^4 log n).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.