Source author record

Diane L. Souvaine

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry math.ST Statistics Theory

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs

We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG $G=(V,E)$ in general position can be augmented to a 2-connected PSLG $(V,E\cup E^+)$ by adding new edges of total Euclidean length $\|E^+\|\leq 2\|E\|$ , and this bound is the best possible. An optimal edge set $E^+$ can be computed in $O(|V|^4)$ time; however the problem becomes NP-hard when $G$ is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG $G=(V,E)$ into a planar straight-line cycle $G'=(V,E')$ such that $\|E'\|\leq 2\|{\rm MST}(V)\|$ , and the graph remains connected with edge length below $\|E\|+\|{\rm MST}(V)\|$ at all stages. These bounds are the best possible.

preprint2015arXiv

Diffuse Reflection Diameter in Simple Polygons

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.

preprint2013arXiv

Bichromatic compatible matchings

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"

preprint2011arXiv

Dynamic Maintenance of Half-Space Depth for Points and Contours

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.