MKMatias Korman

Matias Korman

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

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


Latest Publications

  • Open Access

    Cannibal Animal Games: a new variant of Tic-Tac-Toe

    by Jean Cardinal, Sébastien Collette, Hiro Ito, Matias Korman, Stefan Langerman, Hikaru Sakaidani, Perouz Taslakian

    This paper presents a new partial two-player game, called the \emph{cannibal animal game}, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino $P$ (called an \emph{animal}). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of $P$. An animal is a \emph{cannibal} if Bob has a winning strategy, and a \emph{non-cannibal} otherwise. This paper presents some new tools, such as the \emph{bounding strategy} and the \emph{punching lemma}, to classify animals into cannibals or non-cannibals. We also show that the \emph{pairing strategy} works for this problem.

  • Open Access

    Memory-Constrained Algorithms for Simple Polygons

    by Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, André Schulz

    A constant-workspace algorithm has read-only access to an input array and may use only O(1) additional words of $O(\log n)$ bits, where $n$ is the size of the input. We assume that a simple $n$-gon is given by the ordered sequence of its vertices. We show that we can find a triangulation of a plane straight-line graph in $O(n^2)$ time. We also consider preprocessing a simple polygon for shortest path queries when the space constraint is relaxed to allow $s$ words of working space. After a preprocessing of $O(n^2)$ time, we are able to solve shortest path queries between any two points inside the polygon in $O(n^2/s)$ time.