MKMatias Korman

Matias Korman

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Matias Korman has a total of 77 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Time-Space Trade-offs for Triangulations and Voronoi Diagrams

    by Matias Korman, Wolfgang Mulzer, Andre van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein

    Let $S$ be a planar $n$-point set. A triangulation for $S$ is a maximal plane straight-line graph with vertex set $S$. The Voronoi diagram for $S$ is the subdivision of the plane into cells such that all points in a cell have the same nearest neighbor in $S$. Classically, both structures can be computed in $O(n \log n)$ time and $O(n)$ space. We study the situation when the available workspace is limited: given a parameter $s \in \{1, \dots, n\}$, an $s$-workspace algorithm has read-only access to an input array with the points from $S$ in arbitrary order, and it may use only $O(s)$ additional words of $\Theta(\log n)$ bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic $s$-workspace algorithm for computing an arbitrary triangulation of $S$ in time $O(n^2/s + n \log n \log s )$ and a randomized $s$-workspace algorithm for finding the Voronoi diagram of $S$ in expected time $O((n^2/s) \log s + n \log s \log^*s)$.

  • Routing in polygonal domains

    by Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, Max Willert


  • Graphs with Large Total Angular Resolution

    by Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Parada, Daniel Perz, André van Renssen, Birgit Vogtenhuber


  • Open Access

    Improved Time-Space Trade-offs for Computing Voronoi Diagrams

    by Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein

    Let $P$ be a planar set of $n$ sites in general position. For $k\in\{1,\dots,n-1\}$, the Voronoi diagram of order $k$ for $P$ is obtained by subdividing the plane into cells such that points in the same cell have the same set of nearest $k$ neighbors in $P$. The (nearest site) Voronoi diagram (NVD) and the farthest site Voronoi diagram (FVD) are the particular cases of $k=1$ and $k=n-1$, respectively. For any given $K\in\{1,\dots,n-1\}$, the family of all higher-order Voronoi diagrams of order $k=1,\dots,K$ for $P$ can be computed in total time $O(nK^2+ n\log n)$ using $O(K^2(n-K))$ space [Aggarwal et al., DCG'89; Lee, TC'82]. Moreover, NVD and FVD for $P$ can be computed in $O(n\log n)$ time using $O(n)$ space [Preparata, Shamos, Springer'85]. For $s\in\{1,\dots,n\}$, an $s$-workspace algorithm has random access to a read-only array with the sites of $P$ in arbitrary order. Additionally, the algorithm may use $O(s)$ words, of $\Theta(\log n)$ bits each, for reading and writing intermediate data. The output can be written only once and cannot be accessed or modified afterwards. We describe a deterministic $s$-workspace algorithm for computing NVD and FVD for $P$ that runs in $O((n^2/s)\log s)$ time. Moreover, we generalize our $s$-workspace algorithm so that for any given $K\in O(\sqrt{s})$, we compute the family of all higher-order Voronoi diagrams of order $k=1,\dots,K$ for $P$ in total expected time $O (\frac{n^2 K^5}{s}(\log s+K2^{O(\log^* K)}))$ or in total deterministic time $O(\frac{n^2 K^5}{s}(\log s+K\log K))$. Previously, for Voronoi diagrams, the only known $s$-workspace algorithm runs in expected time $O\bigl((n^2/s)\log s+n\log s\log^* s)$ [Korman et al., WADS'15] and only works for NVD (i.e., $k=1$). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.

  • Gap-planar graphs

    by Sang Won Bae, Jean-Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, et al.


  • Open Access

    Routing in Polygonal Domains

    by Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, Max Willert

    We consider the problem of routing a data packet through the visibility graph of a polygonal domain $P$ with $n$ vertices and $h$ holes. We may preprocess $P$ to obtain a label and a routing table for each vertex of $P$. Then, we must be able to route a data packet between any two vertices $p$ and $q$ of $P$, where each step must use only the label of the target node $q$ and the routing table of the current node. For any fixed $\varepsilon > 0$, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most $1 + \varepsilon$. The labels have $O(\log n)$ bits, and the routing tables are of size $O((\varepsilon^{-1}+h)\log n)$. The preprocessing time is $O(n^2\log n)$. It can be improved to $O(n^2)$ for simple polygons.

  • Time-space trade-offs for triangulations and Voronoi diagrams

    by Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein


  • Open Access

    Dynamic Graph Coloring

    by Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, Sander Verdonschot

    In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} d N^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $\mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(\mathcal{C} d)$-coloring with $O(d N^{1/d})$ recolorings per update. The two converge when $d = \log N$, maintaining an $O(\mathcal{C} \log N)$-coloring with $O(\log N)$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $\Omega(N^\frac{2}{c(c-1)})$ vertices per update, for any constant $c \geq 2$.

  • Open Access

    Geometric Algorithms with Limited Workspace: A Survey

    by Bahareh Banyassady, Matias Korman, Wolfgang Mulzer

    In the limited workspace model, we consider algorithms whose input resides in read-only memory and that use only a constant or sublinear amount of writable memory to accomplish their task. We survey recent results in computational geometry that fall into this model and that strive to achieve the lowest possible running time. In addition to discussing the state of the art, we give some illustrative examples and mention open problems for further research.

  • The dual diameter of triangulations

    by Matias Korman, Stefan Langerman, Wolfgang Mulzer, Alexander Pilz, Maria Saumell, Birgit Vogtenhuber