Diane L. Souvaine

We prove a conjecture of Aanjaneya, Bishnu, and Pal that the minimum number of diffuse reflections sufficient to illuminate the interior of any simple polygon with $n$ walls from any interior point light source is $\lfloor n/2 \rfloor - 1$. Light reflecting diffusely leaves a surface in all directions, rather than at an identical angle as with specular reflections.

For a set $R$ of $n$ red points and a set $B$ of $n$ blue points, a $BR$-matching is a non-crossing geometric perfect matching where each segment has one endpoint in $B$ and one in $R$. Two $BR$-matchings are compatible if their union is also non-crossing. We prove that, for any two distinct $BR$-matchings $M$ and $M'$, there exists a sequence of $BR$-matchings $M = M_1, ..., M_k = M'$ such that $M_{i-1} $ is compatible with $M_i$. This implies the connectivity of the compatible bichromatic matching graph containing one node for each bichromatic matching and an edge joining each pair of compatible matchings, thereby answering the open problem posed by Aichholzer et al. in "Compatible matchings for bichromatic plane straight-line graphs"

Half-space depth (also called Tukey depth or location depth) is one of the most commonly studied data depth measures because it possesses many desirable properties for data depth functions. The data depth contours bound regions of increasing depth. For the sample case, there are two competing definitions of contours: the rank-based contours and the cover-based contours. In this paper, we present three dynamic algorithms for maintaining the half-space depth of points and contours: The first maintains the half-space depth of a single point in a data set in $O(\log n)$ time per update (insertion/deletion) and overall linear space. By maintaining such a data structure for each data point, we present an algorithm for dynamically maintaining the rank-based contours in $O(n\cdot\log n)$ time per update and overall quadratic space. The third dynamic algorithm maintains the cover-based contours in $O(n\cdot \log^2 n)$ time per update and overall quadratic space. We also augment our first algorithm to maintain the local cover-based contours at data points while maintaining the same complexities. A corollary of this discussion is a strong structural result of independent interest describing the behavior of dynamic cover-based contours near data points.