|
 ABSTRACT
Combinatorial and geometric computing is a core area of computer science (CS). In fact, most CS curricula contain a course in data structures and algorithms. The area deals with objects such as graphs, sequences, dictionaries, trees, shortest paths, flows, matchings, points, segments, lines, convex hulls, and Voronoi diagrams and forms the basis for application areas such as discrete optimization, scheduling, traffic control, CAD, and graphics. There is no standard library of the data structures and algorithms of combinatorial and geometric computing. This is in sharp contrast to many other areas of computing. There are, for example, packages in statistics (SPSS), numerical analysis (LINPACK, EISPACK), symbolic computation (MAPLE, MATHEMATICA), and linear programming (CPLEX).
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
|
| |
2
|
|
| |
3
|
Christoph Burnikel , Kurt Mehlhorn , Stefan Schirra, On degeneracy in geometric computations, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.16-23, January 23-25, 1994, Arlington, Virginia, United States
|
| |
4
|
|
| |
5
|
|
| |
6
|
Dijkstra, E.W., A note on two problems in connexion with graphs. Numer. Math 1 (1959), 269-271.
|
| |
7
|
|
| |
8
|
|
| |
9
|
Lauther, U. Untersuchung der library of efficient data types and algoritms (LEDA). Tech. Rep., Siements AG, ZFE, Munchen ,1992.
|
| |
10
|
Locke, N. C++ FTP libraries. C++ Report 6, (1994), 61-65.
|
| |
11
|
Mehlhorn, K. Data Structures and Efficient algoritms. Springer-Verlag, New York, 1984.
|
| |
12
|
Mehlhorn, K., and Naher, S. Algorithm design and software, Architectures, Information Processing 92, vol. 1, Elsevier North-Holland, Amstersam 1992.
|
| |
13
|
Mehlhorn, K., and Naher, S. Implementation of a sweep line algorithm for the segment intersection problem. Tech. Rep. MPI-1-94-160, Max- Planck-Institut fur Informatik, Saarbrucken, 1994.
|
| |
14
|
Mehlhorn, K., and Naher, S. The implementation of geometric algorithms. Thirteenth World Computer Congress. IFIP94, Vol. 1, Elsevier Science North-Holland. Amsterdam, 1994.
|
| |
15
|
Mehlhorn, K., Mutzel, P., and Naher, s. An implementation of the Hopercroft and Tarjan planarity test and embedding algorithm. tech. Rep. MPI-1-93- 151. Max-Planck-Institut fur Informatik, Saarbrucken, 1993.
|
| |
16
|
Muller, M., and Ziegler, J. An implementation of a convex hull algorithm. Tech. Rep. MPI-1-94-105. Max- Planck-Institut fur Informatik. Saarbrucken, 1993.
|
| |
17
|
Naher, S. LEDA manual. Tech. Rep. MPI-1-93-109. Max-Planck-Institut fur Informatik, 1993.
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
| |
22
|
|
| |
23
|
|
CITED BY 64
|
|
|
|
|
V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, United States
|
|
|
Gill Barequet , Stina S. Bridgeman , Christian A. Duncan , Michael T. Goodrich , Roberto Tamassia, Classical computational geometry in GeomNet, Proceedings of the thirteenth annual symposium on Computational geometry, p.412-414, June 04-06, 1997, Nice, France
|
|
|
|
|
|
Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Fully dynamic output bounded single source shortest path problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.212-221, January 28-30, 1996, Atlanta, Georgia, United States
|
|
|
David Alberts , Giuseppe Cattaneo , Giuseppe F. Italiano, An empirical study of dynamic graph algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.192-201, January 28-30, 1996, Atlanta, Georgia, United States
|
|
|
C. Burnikel , R. Fleischer , K. Mehlhorn , S. Schirra, A strong and easily computable separation bound for arithmetic expressions involving square roots, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.702-709, January 05-07, 1997, New Orleans, Louisiana, United States
|
|
|
|
|
|
|
|
|
|
|
|
Michael T. Goodrich , Mark Orletsky , Kumar Ramaiyer, Methods for achieving fast query times in point location data structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.757-766, January 05-07, 1997, New Orleans, Louisiana, United States
|
|
|
|
|
|
Randeep Bhatia , Samir Khuller , Robert Pless , Yoram J. Sussmann, The full degree spanning tree problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.864-865, January 17-19, 1999, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
Kurt Mehlhorn , Michael Müller , Stefan Näher , Stefan Schirra , Michael Seel , Christian Uhrig , Joachim Ziegler, A computational basis for higher-dimensional computational geometry and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.254-263, June 04-06, 1997, Nice, France
|
|
|
Raj Iyer , David Karger , Hariharan Rahul , Mikkel Thorup, An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms, Journal of Experimental Algorithmics (JEA), 6, p.4-es, 2001
|
|
|
|
|
|
C. Burnikel , J. Könemann , K. Mehlhorn , S. Näher , S. Schirra , C. Uhrig, Exact geometric computation in LEDA, Proceedings of the eleventh annual symposium on Computational geometry, p.418-419, June 05-07, 1995, Vancouver, British Columbia, Canada
|
|
|
K. Reinert , H.-P. Lenhof , P. Mutzel , K. Mehlhorn , J. D. Kececioglu, A branch-and-cut algorithm for multiple sequence alignment, Proceedings of the first annual international conference on Computational molecular biology, p.241-250, January 20-23, 1997, Santa Fe, New Mexico, United States
|
|
|
|
|
|
|
|
|
Ali Dasdan , Sandy S. Irani , Rajesh K. Gupta, Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.37-42, June 21-25, 1999, New Orleans, Louisiana, United States
|
|
|
Hans-Peter Lenhof , Knut Reinert , Martin Vingron, A polyhedral approach to RNA sequence structure alignment, Proceedings of the second annual international conference on Computational molecular biology, p.153-162, March 22-25, 1998, New York, New York, United States
|
|
|
|
|
|
Giuseppe Amato , Giuseppe Cattaneo , Giuseppe F. Italiano, Experimental analysis of dynamic minimum spanning tree algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.314-323, January 05-07, 1997, New Orleans, Louisiana, United States
|
|
|
|
|
|
Erez Hartuv , Armin Schmitt , Jörg Lange , Sebastian Meier-Ewert , Hans Lehrach , Ron Shamir, An algorithm for clustering cDNAs for gene expression analysis, Proceedings of the third annual international conference on Computational molecular biology, p.188-197, April 11-14, 1999, Lyon, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T. Hudson , D. Manocha , J. Cohen , M. Lin , K. Hoff , H. Zhang, Accelerated occlusion culling using shadow frusta, Proceedings of the thirteenth annual symposium on Computational geometry, p.1-10, June 04-06, 1997, Nice, France
|
|
|
Marc van Kreveld , Tycho Strijk , Alexander Wolff, Point set labeling with sliding labels, Proceedings of the fourteenth annual symposium on Computational geometry, p.337-346, June 07-10, 1998, Minneapolis, Minnesota, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. Ramos, Randomized external-memory algorithms for some geometric problems, Proceedings of the fourteenth annual symposium on Computational geometry, p.259-268, June 07-10, 1998, Minneapolis, Minnesota, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kurt Mehlhorn , Stefan Näher , Thomas Schilz , Stefan Schirra , Michael Seel , Raimund Seidel , Christian Uhrig, Checking geometric programs or verification of geometric structures, Proceedings of the twelfth annual symposium on Computational geometry, p.159-165, May 24-26, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.2