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.
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$).
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].
We consider a one-round two-player network pricing game, the Stackelberg
Minimum Spanning Tree game or StackMST.