James King

Postdoctoral Research Assistant   Imperial College London     Department of Mathematics

Welcome to my home page.  Since October, 2010 I have been a postdoctoral researcher in the research group of Nick Jones, starting in the Department of Physics at the University of Oxford, then moving to the Department of Mathematics at Imperial College London at the start of 2012.  I do research in various areas of theoretical computer science.  In my current position my research focuses on the landscapes of combinatorial objects and optimization algorithms.

Research Interests

• combinatorial optimization
• computational geometry
• discrete geometry
• bioinformatics
• data structures
• probabilistic analysis

Submitted Works

Generating k-Facets by Induction on the Dimension James King Submitted to Symposium on Computational Geometry (SoCG 2012). Preprint submitted to arXiv.org.

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 James King Submitted to Computational Geometry: Theory and Applications. Preprint submitted to arXiv.org.

Publications

	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 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.

Ph.D. Thesis

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

Curriculum Vitae

A PDF version of my CV, last updated January 2012.

Stuff

• Fair Vote Canada
• A list of useful inequalities