Related papers

Near-linear approximation algorithms for geometric hitting sets.
Pankaj Agarwal, Esther Ezra, and Micha Sharir.
2008.

Small-size eps-nets for axis-parallel rectangles and boxes.
Boris Aronov, Esther Ezra, and Micha Sharir.
2008.

Linear-time triangulation of a simple polygon made easier via randomization.
Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos.
In SCG '00: Proceedings of the sixteenth annual symposium on Computational geometry, pages 201--212, New York, NY, USA, 2000. ACM Press.

Parallel linear programming in fixed dimension almost surely in constant time.
N. Alon and N. Megiddo.
In Proc. 31st IEEE Symp. on Foundations of Computer Science, pages 574--582, 1990.

A randomization scheme for speeding up algorithms for linear and convex quadratic programming problems with a high constraints-to-variables ratio.
I. Adler and R. Shamir.
Math. Prog., 61:39--52, 1993.
Preliminary version in Rutgers Univ. Tech. Report, 1990.

Almost optimal set covers in finite VC-dimension.
H. Br{\"o}nnimann and M. T. Goodrich.
In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 293--302, 1994.

Computational discovery of gene modules and regulatory networks.
Ziv Bar-Joseph, Georg K. Gerber, Tong Ihn Lee, Nicola J. Rinaldi, Jane Y. Yoo, François Robert, D. Benjamin Gordon, Ernest Fraenkel, Tommi S. Jaakkola, Richard A. Young, and David K. Gifford.
Nature Biotechnology, 21:1337--1342, 2003.

Uncertain convex programs: Randomized solutions and confidence levels.
G. Calafiore and M.C. Campi.
Mathematical Programming, 102(1):25--46, 2005.

Multi-pass geometric algorithms.
Timothy M. Chan and Eric Y. Chen.
In Proc. 21st ACM Symposium on Computational Geometry, pages 180--189, 2005.

Triangulating a simple polygon in linear time.
Bernard Chazelle.
Discrete \& Computational Geometry, 6(5):485--524, 1991.

Output-sensitive results on convex hulls, extreme points, and related problems.
Timothy M. Chan.
In SCG '95: Proceedings of the Eleventh annual symposium on Computational geometry, pages 10--19, New York, NY, USA, 1995. ACM Press.

A decomposition of multidimensional point sets with applications to `k`-nearest-neighbors and `n`-body problems.
P. B. Callahan and S. R. Kosaraju.
J. Assoc. Comput. Mach., 42:67--90, 1995.

Sublinear geometric algorithms.
Bernard Chazelle, Ding Liu, and Avner Magen.
In Annual {ACM} Symposium on Theory of Computing, 2003.

On linear-time deterministic algorithms for optimization problems in fixed dimension.
B. Chazelle and J. Matou{\v s}ek.
In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 281--290, 1993.

Cuttings and applications.
Mark de Berg and Otfried Schwarzkopf.
Internat. J. Comput. Geom. Appl, 1992.

Sample compression, learnability, and the Vapnik-Chervonenkis dimension.
Sally Floyd and Manfred Warmuth.
Machine Learning, 21(3):269--304, 1995.

Fast construction of nets in low dimensional metrics, and their applications.
S. Har-Peled and M. Mendel.
In {SOCG} '05: Proceedings of the Twenty-First Annual Symposium on Computational Geometry, 2005.

$\epsilon$-nets and simplex range queries.
David Haussler and Emo Welzl.
Discrete \& Computational Geometry, 2:127--152, 1987.
Preliminary version in SOCG '86: Proceedings of the Second Annual Symposium on Computational Geometry, 1986.

A subexponential randomized simplex algorithm.
G. Kalai.
In Proc. 24th Annu. ACM Sympos. Theory Comput., pages 475--482, 1992.

Classes of graphs which approximate the complete Euclidean graph.
J. Mark Keil and Carl A. Gutwin.
Discrete \& Computational Geometry, 7(1):13--28, 1992.

Navigating nets: simple algorithms for proximity search.
R. Krauthgamer and J. R. Lee.
In SODA '04: Proceedings of the Fifteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms, pages 798--807. Society for Industrial and Applied Mathematics, 2004.

How good is the simplex algorithm?.
V. Klee and G. J. Minty.
In Inequalities III, pages 159--175. Academic Press, 1972.

Finding nearest neighbors in growth-restricted metrics.
D. R. Karger and M. Ruhl.
In {STOC} '02: Proceedings of the Thirty-Fourth Annual {ACM} Symposium on Theory of Computing, pages 741--750. ACM Press, 2002.

A subexponential bound for linear programming.
J. Matou{\v s}ek, M. Sharir, and E. Welzl.
In Proc. 8th Annu. ACM Sympos. Comput. Geom., pages 1--8, 1992.

A generalization of Dehn-Sommerville relations to simple stratified spaces.
Ketan Mulmuley.
Discrete \& Computational Geometry, 9:47--55, 1993.

On approximating the smallest enclosing Bregman balls.
Frank Nielsen and Richard Nock.
In SCG '06: Proceedings of the Twenty-Second Annual Symposium on Computational geometry, pages 485--486, New York, NY, USA, 2006. ACM Press.

Enumerating extreme points in higher dimensions.
T. Ottmann, S. Schuierer, and S. Soundaralakshmi.
In Proc. 12th Sympos. Theoret. Aspects Comput. Sci. (STACS), volume 900 of Lecture Notes in Computer Science, pages 562--570. Springer-Verlag, 1995.

Approximating the `d`-dimensional complete Euclidean graph.
J. Ruppert and R. Seidel.
In Canadian Conference on Computational geometry, pages 207--210, 1991.

Small-dimensional linear programming and convex hulls made easy.
R. Seidel.
Discrete \& Computational Geometry, pages 423--433, 1991.

A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons.
Raimund Seidel.
Comput. Geom. Theory Appl., 1(1):51--64, 1991.

Core vector regression for very large regression problems.
Ivor W. Tsang, James T. Kwok, and Kimo T. Lai.
In ICML '05: Proceedings of the 22nd international conference on Machine learning, pages 912--919, New York, NY, USA, 2005. ACM Press.

An `{:O:}(n log n)` algorithm for the all-nearest-neighbors problem.
P. M. Vaidya.
Discrete \& Computational Geometry, 4(2):101--115, 1989.