Stefan Langerman

  1. Confluent Persistence Revisited.

    Authors: Stefan Langerman, John Iacono, Sebastien Collette
    Subjects: Data Structures and Algorithms
    Abstract

    It is shown how to enhance any data structure in the pointer model to make it
    confluently persistent, with efficient query and update times and limited space
    overhead. Updates are performed in $O(\log n)$ amortized time, and following a
    pointer takes $O(\log c \log n)$ time where $c$ is the in-degree of a node in
    the data structure. In particular, this proves that confluent persistence can
    be achieved at a logarithmic cost in the bounded in-degree model used widely in
    previous work.

  2. Blocking Coloured Point Sets.

    Authors: Stefan Langerman, David R. Wood, Brad Ballinger, Sébastien Collette, Attila Pór, Greg Aloupis
    Subjects: Combinatorics
    Abstract

    This paper studies problems related to visibility among points in the plane.
    A point $x$ \emph{blocks} two points $v$ and $w$ if $x$ is in the interior of
    the line segment $\bar{vw}$. A set of points $P$ is \emph{$k$-blocked} if each
    point in $P$ is assigned one of $k$ colours, such that distinct points $v,w\in
    P$ are assigned the same colour if and only if some other point in $P$ blocks
    $v$ and $w$. The focus of this paper is the conjecture that each $k$-blocked
    set has bounded size (as a function of $k$).

  3. Every Large Point Set contains Many Collinear Points or an Empty Pentagon.

    Authors: Stefan Langerman, Ferran Hurtado, David R. Wood, Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Scott D. Kominers, Attila Pór
    Subjects: Combinatorics
    Abstract

    We prove the following generalised empty pentagon theorem: for every integer
    $\ell \geq 2$, every sufficiently large set of points in the plane contains
    $\ell$ collinear points or an empty pentagon. As an application, we settle the
    next open case of the "big line or big clique" conjecture of K\'ara, P\'or, and
    Wood [\emph{Discrete Comput. Geom.} 34(3):497--506, 2005].

  4. The Stackelberg Minimum Spanning Tree Game.

    Authors: Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann, Stefan Langerman
    Subjects: Computer Science and Game Theory
    Abstract

    We consider a one-round two-player network pricing game, the Stackelberg
    Minimum Spanning Tree game or StackMST.

Syndicate content