登入選單

返回Google圖書搜尋

Backwards Analysis of Randomized Geometric Algorithms

International Computer Science InstituteRaimund Seidel

出版	International Computer Science Institute, 1992
URL	http://books.google.com.hk/books?id=L1fzGwAACAAJ&hl=&source=gbs_api

註釋

Abstract: "The theme of this paper is a rather simple method that has proved very potent in the analysis of the expected performance of various randomized algorithms and data structures in computational geometry. The method can be described as 'analyze a randomized algorithm as if it were running backwards in time, from output to input.' We apply this type of analysis to a variety of algorithms, old and new, and obtain solutions with optimal or near optimal expected performance for a plethora of problems in computational geometry, such as computing Delaunay triangulations of convex polygons, computing convex hulls of point sets in the plane or in higher dimensions, sorting, intersecting line segments, linear programming with a fixed number of variables, and others."