Showing 1999Show all
2 papers · 1 filter
math.CO1999
The Average-Case Area of Heilbronn-Type Triangles
Tao Jiang, Ming Li, Paul Vitanyi
From among triangles with vertices chosen from points in the unit square, let be the one with the smallest area, and let be the area of . Heilbronn'…
cs.DS1999
Average-Case Complexity of Shellsort
Tao Jiang, Ming Li, Paul Vitanyi
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a -pass Shellsort for any incremental…