Randomization and Derandomization

Authored by: Otfried Cheong , Ketan Mulmuley , Edgar Ramos

Discrete and Computational Geometry

Print publication date:  April  2004
Online publication date:  April  2004

Print ISBN: 9781584883012
eBook ISBN: 9781420035315
Adobe ISBN:

10.1201/9781420035315.ch40

 Download Chapter

 

Abstract

Randomized (or probabilistic) algorithms and constructions were applied successfully in many areas of theoretical computer science before they were used widely in computational geometry. Following influential work in the mid-1980s, randomized algorithms became popular in geometry, and now a significant proportion of published research in computational geometry employs randomized algorithms or proof techniques. For many problems the best algorithms known are randomized, and even if both randomized and deterministic algorithms of comparable asymptotic complexity are available, the randomized algorithms are often much simpler and more efficient in an actual implementation. In some cases, the best deterministic algorithm known for a problem has been obtained by “derandomizing” a randomized algorithm.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.