The Anatomy of a Geometric Algorithm

Matousek, Jirí (1999) The Anatomy of a Geometric Algorithm. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 1-7 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_1).

Full text not available from this repository.

Abstract

This article contains the speaker’s slides for the talk, reproduced by the editors with speaker’s permission. An appendix with references was prepared by the speaker.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_1
Classifications:Z Theory > Z.250 Geometry
ID Code:233

Repository Staff Only: item control page

References

A. Datta, H.-P. Lenhof, C. Schwarz, and M. Smid. Static and dynamic algorithms for k-point clustering problems. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes Comput. Sci., pages 265-276. Springer-Verlag, 1993.

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.

A. Efrat, M. Sharir, and A. Ziv. Computing the smallest k-enclosing circle and related problems. Comput. Geom. Theor. Appl., 4:119-136, 1994.

D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 64-73, 1993.

A. Gajentaan and M. H. Overmars. On a class of n^{2}-hard problems in computational geometry. Comput. Geom. Theor. Appl., 5(3):117-142, 1995.

J. E. Goodman and J. O'Rourke, editors. Handbook of Discrete and Computational Geometry. CRC Press LLC, Boca Raton, FL, 1997.

J. Matousek. On geometric optimization with few violated constraints. Discrete Comput. Geom., 14:365-384, 1995.

J. Matousek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16:498-516, 1996.

J. Matousek. On enclosing k points by a circle. Information Processing Letters, 53:217-221, 1995.

N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30:852-865, 1983.

J.-R. Sack and J. Urrutia, editors. Handbook on Computational Geometry. North-Holland, 1999. In press.