Ken Clarkson

Kenneth L. Clarkson (Ken)

Distinguished Member of Technical Staff

Bell Laboratories, Lucent Technologies

Room 2C-526

600 Mountain Ave.

Murray Hill, NJ 07974 USA

Office: 908 582 4717

Fax: 908 582 3340

clarkson@alcatel-lucent.com

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:

• related to linear, convex, and integer programming in small dimension
• center points
• a short, complete planar convex hull code

My bibliography

Sadly, I haven't managed to:

• Direct Law and Economics Centers
• Play the banjo in Jimmy Chickenpants
• Be a bashful crooner whose career succeeds using the contributions of his girlfriend, who had received a million dollars from a mysterious reclusive billionaire, and who becomes afraid she has lost him, and to whom he at last returns
• Be a former agent of the spider-aliens
• Be an alter ego of Superman,  or of an imaginary Superman