C. Levcopoulos

activity

20102024

collaborators

9 papers

cs.CG2024

The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O (lo g n)$ Deterministic Rounds on the Congested Clique

Jesper Jansson, Christos Levcopoulos, Andrzej Lingas

We study the problem of computing the Voronoi diagram of a set of $n^{2}$ points with $O (lo g n)$ -bit coordinates in the Euclidean plane in a substantially sublinear in $n$ number of…

cs.DC2023

Convex Hulls, Triangulations, and Voronoi Diagrams of Planar Point Sets on the Congested Clique

Jesper Jansson, Christos Levcopoulos, Andrzej Lingas +1

We consider geometric problems on planar $n^{2}$ -point sets in the congested clique model. Initially, each node in the $n$ -clique network holds a batch of $n$ distinct points in the…

cs.DS2022

Perpetual maintenance of machines with different urgency requirements

Leszek Gąsieniec, Tomasz Jurdziński, Ralf Klasing +4

A garden $G$ is populated by $n \geq 1$ bamboos $b_{1}, b_{2}, ..., b_{n}$ with the respective daily growth rates $h_{1} \geq h_{2} \geq \dots \geq h_{n}$ . It is assumed that the initial heights of…

cs.DC2021

Efficient Assignment of Identities in Anonymous Populations

Leszek Gasieniec, Jesper Jansson, Christos Levcopoulos +1

We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the s…

cs.CG2019

Local Routing in Sparse and Lightweight Geometric Graphs

Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos +2

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 r…

math.MG2016

Shortcuts for the Circle

Sang Won Bae, Mark de Berg, Otfried Cheong +2

Let $C$ be the unit circle in $R^{2}$ . 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 lengt…

cs.DS2016

Efficiently Correcting Matrix Products

Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas +2

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…

cs.CG2014

A Fire Fighter's Problem

Rolf Klein, Elmar Langetepe, Christos Levcopoulos

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 cont…

cs.CG2010

Quickest Path Queries on Transportation Network

Radwa El Shawi, Joachim Gudmundsson, Christos Levcopoulos

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…