Ken Clarkson

I left Lucent in January 2007, so this page is "historical"; I can be contacted at the gmail address below.

photo Kenneth L. Clarkson (Ken)
Bell Laboratories, Lucent Technologies
Room 2C-526
600 Mountain Ave.
Murray Hill, NJ 07974 USA
Office: 908 582 4717
Fax: 908 582 3340

I am a member of the Mathematical and Algorithmic Sciences Research Center.

My work has mainly been on geometric algorithms, and in particular on algorithms that have provable properties, but are relatively simple. Randomization is quite useful for this, whether via the Vapnik-Chervonenkis dimension, or using the general framework introduced here. See, for example, a survey on randomized geometric algorithms.

Ocelot has been a major project for the last several years.

I've coded up a data structure for nearest neighbor searching in metric spaces, which supports nearest neighbor queries, fixed radius queries, and k'th-nearest-neighbor queries. I've tested it on Euclidean data, strings under Hamming and edit distances, and some bitvector datasets. It gives a pretty good speedup for low-dimensional data, and sometimes high-dimensional data, but isn't going to be as fast as more specialized methods.

I've coded up a program for computing convex hulls, Delaunay triangulations, alpha shapes, and related information; this uses a simple randomized incremental algorithm, and an algorithm of mine that allows some matrix operations using exact arithmetic to be done quickly.

Some other software of mine, not necessarily the most polished:

I am co-moderator of the compgeom-announce mailing list, for announcements regarding computational geometry, and the list compgeom-discuss, for discussions. These lists were formerly here, within netlib, but through the efforts of Hervé Brönnimann are now hosted at Polytechnic U.

My bibliography

Sadly, I haven't managed to:

And finally, sometimes we must bite the bull by the horns.
Last modified: January 2007.