(*^ ::[paletteColors = 128; fontset = title, "New York", 18, L2, center, bold, nohscroll; fontset = subtitle, "New York", 14, L2, center, bold, nohscroll; fontset = subsubtitle, "New York", 14, L2, center, bold, nohscroll; fontset = section, "New York", 12, L2, bold, nohscroll, grayBox; fontset = subsection, "New York", 10, L2, bold, nohscroll, blackBox; fontset = subsubsection, "New York", 10, L2, bold, nohscroll, whiteBox; fontset = text, "New York", 9, L2, nohscroll; fontset = smalltext, "New York", 10, L2, nohscroll; fontset = input, "Courier", 10, L2, bold, nowordwrap; fontset = output, "Courier", 10, L2, nowordwrap; fontset = message, "Courier", 12, L2, R65535, nowordwrap; fontset = print, "Courier", 12, L2, nowordwrap; fontset = info, "Courier", 12, L2, nowordwrap; fontset = postscript, "Courier", 12, L2, nowordwrap; fontset = name, "Geneva", 10, L2, italic, B65535, nowordwrap, nohscroll; fontset = header, "Times", 10, L2; fontset = footer, "Times", 12, L2, center; fontset = help, "Geneva", 10, L2, nohscroll; fontset = clipboard, "New York", 12, L2; fontset = completions, "New York", 12, L2, nowordwrap; fontset = network, "Courier", 10, L2, nowordwrap; fontset = graphlabel, "Courier", 12, L2, nowordwrap; fontset = special1, "New York", 12, L2, nowordwrap; fontset = special2, "New York", 12, L2, center, nowordwrap; fontset = special3, "New York", 12, L2, right, nowordwrap; fontset = special4, "New York", 12, L2, nowordwrap; fontset = special5, "New York", 12, L2, nowordwrap;] :[font = title; inactive; startGroup; ] Computational Geometry :[font = subsubtitle; inactive; ] Steven S. Skiena Department of Computer Science State University of New York Stony Brook, NY 11794 (516) 632-9026/8470 skiena@sbcs.sunysb.edu ;[s] 2:0,1;1,0;145,-1; 2:1,19,14,New York,1,14,0,0,0;1,19,14,New York,0,14,0,0,0; :[font = text; inactive; ] This package provides Mathematica implementations for several important algorithms and structures in Computational Geometry. It is written as an extension of Combinatorica, the author's package for combinatorics and graph theory, described in [1]. Each geometric object is represented as a graph structure, where the adjacency information is represented by an adjacency matrix and the points by a list of {x,y} pairs. ;[s] 5:0,0;22,1;33,0;407,1;412,0;420,-1; 2:3,14,10,New York,0,9,0,0,0;2,12,10,New York,2,9,0,0,0; :[font = text; inactive; ] All implementations of geometric algorithms are subject to numerical instabilities, and robust geometric computation is an area of active research. In this package, we make the standard assumptions that the points are in general position, meaning no three vertices are collinear. Further, we assume that no two vertices have the same x or y-coordinate. While these conditions hold with probability one on random data, these assumptions are inappropriate for certain applications. We recommend perturbing non-random data slightly using the Combinatorica function ShakeGraph with an appropriately small constant, which will eliminate degeneracies while maintaining the combinatorial structure of the arrangement. ;[s] 5:0,0;336,1;337,0;341,1;342,0;715,-1; 4:3,14,10,New York,0,9,0,0,0;2,12,10,New York,2,9,0,0,0;0,12,10,New York,1,9,0,0,0;0,12,10,New York,3,9,0,0,0; :[font = text; inactive; ] [1] S. S. Skiena, 'Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica', Addison-Wesley, Reading MA, 1990. ;[s] 3:0,0;19,1;101,0;138,-1; 2:2,14,10,New York,0,9,0,0,0;1,12,10,New York,2,9,0,0,0; :[font = input; initialization; ] *) <