73 citations · 387 across the 61 of their papers we have counts for
4 papers · 1 filter
Visibility-Monotonic Polygon Deflation
Prosenjit Bose, Vida Dujmović, Nima Hoda +1
A deflated polygon is a polygon with no visibility crossings. We answer a question posed by Devadoss et al. (2012) by presenting a polygon that cannot be deformed via continuous vi…
Approximating Majority Depth
Dan Chen, Pat Morin
We consider the problem of approximating the majority depth (Liu and Singh, 1993) of a point q with respect to an n-point set, S, by random sampling. At the heart of this problem i…
Robust Geometric Spanners
Prosenjit Bose, Vida Dujmovic, Pat Morin +1
Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely applicable and extensively studied combinatorial objects. We initiate…
A Note on Interference in Random Point Sets
Luc Devroye, Pat Morin
The (maximum receiver-centric) interference of a geometric graph (von Rickenbach etal (2005)) is studied. It is shown that, with high probability, the following results hold for a…