4 citations · 10 across the 8 of their papers we have counts for
8 papers
The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS
Stephan Friedrichs, Michael Hemmer, James King +1
In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an -monotone chain of line segments in (the terrain ) and ask for the minimum number…
Generating k-Facets by Induction on the Dimension
James King
Let S be a set of n >= d points in general position in R^d. An oriented (d-1)-simplex spanned by d points from S is called a k-facet iff the positive side of its affine hull contai…
Random hyperplane search trees in high dimensions
Luc Devroye, James King
Given a set S of n \geq d points in general position in R^d, a random hyperplane split is obtained by sampling d points uniformly at random without replacement from S and splitting…
Fast Vertex Guarding for Polygons
James King
For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of P's vertices such that every point in P is seen by at least one point in G. This probl…
Odds-On Trees
Prosenjit Bose, Luc Devroye, Karim Douieb +3
Let R^d -> A be a query problem over R^d for which there exists a data structure S that can compute P(q) in O(log n) time for any query point q in R^d. Let D be a probability measu…
Improved Approximation for Guarding Simple Galleries from the Perimeter
James King, David Kirkpatrick
We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for buil…