Kenneth L. Clarkson

Ken Clarkson på SoCG 2011

Kenneth Lee Clarkson är en amerikansk datavetare känd för sin forskning inom beräkningsgeometri . Han är forskare vid IBM Almaden Research Center och medredaktör för Journal of Computational Geometry .

Biografi

Clarkson fick sin Ph.D. från Stanford University 1984, under ledning av Andrew Yao . Fram till 2007 arbetade han för Bell Labs .

1998 var han medordförande för ACM Symposium on Computational Geometry .

Forskning

Clarksons huvudsakliga forskningsintressen är beräkningsgeometri .

Hans mest citerade artikel, med Peter Shor , använder slumpmässigt urval för att ta fram optimala randomiserade algoritmer för flera problem med att konstruera geometriska strukturer, uppföljning på en tidigare ensamförfattad artikel av Clarkson om samma ämne. Den innehåller algoritmer för att hitta alla $k$ skärningspunkter bland en uppsättning av $n$ linjesegment i planet under förväntad tid $O(k+n\log n)$ , hitta diametern för en uppsättning av $n$ punkter i tre dimensioner i förväntad tid $O(n\log n)$ , och konstruera det konvexa skrovet på $n$ punkter i $d$ -dimensionellt euklidiskt rum i förväntad tid $O(n^{\lfloor d/2\rfloor } +n\log n)$ . Samma papper använder också slumpmässigt urval för att bevisa gränser i diskret geometri , och i synnerhet för att ge snäva gränser för antalet ≤ k - uppsättningar .

Clarkson har också skrivit mycket citerade artiklar om komplexiteten i arrangemang av kurvor och ytor, sökning av närmaste grannar , rörelseplanering och lågdimensionell linjär programmering och problem av LP-typ .

Pris och ära

2008 valdes Clarkson till Fellow i ACM för sina "bidrag till beräkningsgeometri."

externa länkar

• Clarksons webbsida hos IBM