Publications

Publications

Random Hyperplane Search Trees in High Dimensions
Luc Devroye and James King
Submitted to Journal of Computational Geometry. Preprint submitted to arXiv.org.
Fast Vertex Guarding for Polygons with and without Holes
James King
Computational Geometry: Theory and Applications, Volume 46, Issue 3, pp. 219–231 (2013).
Discrete Optimization and Data Analysis: An Empirical Approach to Landscapes
James King and Nick Jones
In proceedings of MIC 2011: The 9th Metaheuristics International Conference.
Terrain Guarding is NP-Hard
James King and Erik Krohn
SIAM Journal on Computing, 40(5), pp. 1316–1339,.
Improved Approximation for Guarding Simple Galleries from the Perimeter
James King and David Kirkpatrick
Discrete and Computational Geometry, to appear. Preprint submitted to arXiv.org.
Fast Motif Recognition via Application of Statistical Thresholds
Christina Boucher and James King
BMC Bioinformatics 2010, 11(Suppl 1):S11.
Terrain Guarding is NP-Hard
James King and Erik Krohn
In proceedings of SODA10.
Random Hyperplane Search Trees
Luc Devroye, James King, and Colin McDiarmid.
SIAM Journal on Computing, Volume 38, Issue 6, pp. 2411-2425 (2009).
VC-Dimension of Visibility on Terrains
James King
In proceedings of CCCG 2008, pp. 27-30.
Realization of Degree 10 Minimum Weight Spanning Trees in 3-Space
James King
In proceedings of CCCG 2006, pp. 39-42. (Full version )
Minimizing the Number of Arcs Linking a Permutation of Points in the Plane
Stéphane DurocherChris Gray, and James King
In proceedings of CCCG 2006, pp. 181-184.
A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
James King
Lecture Notes in Computer Science (3887), pp. 629-640, 2006.
Fun-Sort–or the Chaos of Unordered Binary Search
Therese BiedlTimothy ChanErik D. DemaineRudolf FleischerMordecai Golin, James A. King, and J. Ian Munro
Discrete Applied Mathematics, volume 144, number 3, December 2004, pages 231-236.

Ph.D. Thesis

Guarding Problems and Geometric Split Trees
James King
Ph.D. Thesis, McGill University, 2010.