Lehigh University - CSE: Clarkson

Kenneth Clarkson

"Metric Space Epsilon-nets & Their Applications"

Thursday, October 5, 4:00 PM

Packard Lab -- Room 360

Metric spaces are very simple geometric structures: they comprise a set and a distance measure that obeys the triangle inequality. å-nets, also called "low-dispersion sets" or "farthest-point samples", are subsets of metric spaces that are "well-distributed" in a certain sense. They can be found efficiently using a greedy algorithm. This talk will review that algorithm, and briefly survey applications of å-nets in motion planning, nearest neighbor searching, building meshes to approximate curves and surfaces, and building
triangulations to approximate functions.

Ken Clarkson is a member of the technical staff in the Mathematical and Algorithmic Sciences at Bell Laboratories. His work focuses on algorithmic problems in a geometric setting, such as nearest-neighbor searching and computing convex hulls, but has also included work in optimization of cellular phone systems and backbone networks. He introduced a framework for the use of randomization in geometric algorithms that is similar to, but not the same as, the VC dimension.

		Kenneth Clarkson "Metric Space Epsilon-nets & Their Applications" Thursday, October 5, 4:00 PM Packard Lab -- Room 360 Metric spaces are very simple geometric structures: they comprise a set and a distance measure that obeys the triangle inequality. å-nets, also called "low-dispersion sets" or "farthest-point samples", are subsets of metric spaces that are "well-distributed" in a certain sense. They can be found efficiently using a greedy algorithm. This talk will review that algorithm, and briefly survey applications of å-nets in motion planning, nearest neighbor searching, building meshes to approximate curves and surfaces, and building triangulations to approximate functions. Ken Clarkson is a member of the technical staff in the Mathematical and Algorithmic Sciences at Bell Laboratories. His work focuses on algorithmic problems in a geometric setting, such as nearest-neighbor searching and computing convex hulls, but has also included work in optimization of cellular phone systems and backbone networks. He introduced a framework for the use of randomization in geometric algorithms that is similar to, but not the same as, the VC dimension.