Research Interests

I am primarily interested in computational geometry, especially guarding problems. I'm also interested in data structures & algorithms and several other areas of theory. At McGill I'm doing a fair amount of probabilistic analysis of algorithms and randomized algorithms, and I am starting to dabble in combinatorial geometry.

Publications

	Fast Motif Recognition via Application of Statistical Thresholds Christina Boucher and James King Accepted to APBC 2010.
	Terrain Guarding is NP-Hard James King and Erik Krohn Accepted to 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.
	Neighbourhood Thresholding for Projection-Based Motif Discovery James King, Warren Cheung, and Holger H. Hoos Accepted to Bioinformatics pending revisions.
	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 Durocher, Chris 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 Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, and J. Ian Munro Discrete Applied Mathematics, volume 144, number 3, December 2004, pages 231-236.

Conference Talks

	VC-Dimension of Visibility on Terrains CCCG 2008: 20th Canadian Conference on Computational Geometry, Montreal, Canada, August 13-15, 2008.
	Realization of Degree 10 Minimum Spanning Trees in 3-Space CCCG 2006: 18th Canadian Conference on Computational Geometry, Kingston, Canada, August 14-16, 2006.
	A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006.

Unpublished Projects

[2005/08]		Approximation Algorithms for Guarding 1.5-Dimensional Terrains (Master's Thesis)
[2004/12]		Origami-Constructible Numbers (survey paper)
[2004/04]		Succinct Data Structures for Tree Adjoining Grammars
[2003/12]		A Survey of 3SUM-Hard Problems (survey paper)
[2003/04]		Conductance and Rapidly Mixing Markov Chains (survey paper)

Curriculum Vitae