{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T07:10:41Z","timestamp":1683011441880},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,4]]},"DOI":"10.1007\/bf01187021","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T14:04:39Z","timestamp":1108735479000},"page":"404-428","source":"Crossref","is-referenced-by-count":11,"title":["A workbench for computational geometry"],"prefix":"10.1007","volume":"11","author":[{"given":"P.","family":"Epstein","sequence":"first","affiliation":[]},{"given":"J.","family":"Kavanagh","sequence":"additional","affiliation":[]},{"given":"A.","family":"Knight","sequence":"additional","affiliation":[]},{"given":"J.","family":"May","sequence":"additional","affiliation":[]},{"given":"T.","family":"Nguyen","sequence":"additional","affiliation":[]},{"given":"J. -R.","family":"Sack","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0031-3203(84)90064-5","volume":"17","author":"F. Aurenhammer","year":"1984","unstructured":"F. Aurenhammer and H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane,Pattern Recognition,17 (1984), 251?275.","journal-title":"Pattern Recognition"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"C. R. Aragon and R. G. Seidel, Randomized binary search trees,Proc. 30th Symposium on Foundations of Computer Science, pp. 450?455, 1989.","DOI":"10.1109\/SFCS.1989.63531"},{"key":"CR3","unstructured":"M. D. Atkinson and J.-R. Sack, Uniform generation of combinatorial objects in parallel,J. Parallel Distributed Comput. (1993), to appear."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(92)90075-7","volume":"41","author":"M. D. Atkinson","year":"1992","unstructured":"M. D. Atkinson and J.-R. Sack. Generating binary trees at random,Inform. Process. Lett.,41 (1992), 21?23.","journal-title":"Inform. Process. Lett."},{"key":"CR5","unstructured":"M. D. Atkinson and J.-R. Sack, Uniform Generation of Forests of Restricted Height, Technical Report TR-230, School of Computer Science, Carleton University, 1993."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"J. Culberson and G. Rawlins, Turtlegons: generating simple polygons from sequences of angles,Proc. 1st ACM Symposium on Computational Geometry, pp. 305?310, 1985.","DOI":"10.1145\/323233.323272"},{"key":"CR7","unstructured":"L. Devroye, Private communication, McGill University, Novemeber, 1991."},{"key":"CR8","unstructured":"T. Doe and S. Edwards, Course Project: Random Generation of Polygons, Report 95.508, Carleton University, 1984."},{"issue":"3","key":"CR9","doi-asserted-by":"crossref","first-page":"291","DOI":"10.2307\/1390647","volume":"2","author":"L. Devroye","year":"1993","unstructured":"L. Devroye, P. Epstein, and J.-R. Sack, On generating random intervals and hyperrect-angles,J. Comput. Graphical Statis.,2(3) (1993), 291?307.","journal-title":"J. Comput. Graphical Statis."},{"key":"CR10","volume-title":"EATCS Monographs on Theoretical Computer Science, Vol. 10","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, Vol. 10 (W. Brauer, G. Rozenberg, and A. Salomaa, eds.), Springer-Verlag, New York, 1987."},{"key":"CR11","unstructured":"P. Epstein, Polygon Shortest Path Algorithms and Applications, 4th year Honours Thesis, Carleton University, May 1990."},{"key":"CR12","unstructured":"P. Epstein, Generation of Random Geometric Objects, M.Sc. thesis, Carleton University, April 1992."},{"key":"CR13","unstructured":"P. Epstein and J.-R. Sack, Generating triangulations at random,Proc. 4th Canadian Conference in Computational Geometry, 1992, pp. 305?310."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/978-1-4613-8713-8_4","volume-title":"Techniques for Computer Graphics","author":"A. R. Forrest","year":"1987","unstructured":"A. R. Forrest, Computational geometry and software engineering, towards a geometric computing environment, inTechniques for Computer Graphics (D. F. Rogers and R. A. Earnshaw, eds.), Springer-Verlag, New York, 1987, pp. 23?37."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"S. Fortune, A sweepline algorithm for Voronoi diagrams,Algorithmica,2 (1987), 153?174.","journal-title":"Algorithmica"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/357337.357341","volume":"3","author":"A. Fournier","year":"1984","unstructured":"A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Trans. Graphics,3 (1984), 153?174.","journal-title":"ACM Trans. Graphics"},{"key":"CR17","volume-title":"Smalltalk-80: The Language and Its Implementation","author":"A. Goldberg","year":"1983","unstructured":"A. Goldberg and D. Robson,Smalltalk-80: The Language and Its Implementation, Addison-Wesley, Reading, MA, 1983."},{"issue":"2","key":"CR18","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons,Algorithmica,2(2) (1987), 209?233.","journal-title":"Algorithmica"},{"issue":"4","key":"CR19","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M. Garey","year":"1978","unstructured":"M. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Inform. Process. Lett.,7(4) (1978), 175?180.","journal-title":"Inform. Process. Lett."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set,Inform. Process. Lett,1 (1972), 132?133.","journal-title":"Inform. Process. Lett"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddieston","year":"1982","unstructured":"S. Huddieston and K. Mehlhorn, A new data structure for representing sorted lists,Acta Inform.,17 (1982), 157?184.","journal-title":"Acta Inform."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/S0019-9958(86)80033-X","volume":"68","author":"K. Hoffman","year":"1986","unstructured":"K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. Tarjan Sorting Jordan sequences in linear time using level-linked search trees,Inform, and Control,68 (1986), 170?184.","journal-title":"Inform, and Control"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","volume":"2","author":"R. A. Jarvis","year":"1973","unstructured":"R. A. Jarvis, On the identification of the convex hull of a finite set of points in the plane,Inform. Process. Lett.,2 (1973), 18?21.","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"CR24","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D. G. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput.,12(1) (1983), 28?35.","journal-title":"SIAM J. Comput."},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"A. Knight, A Computational Geometry Workbench and Its Use in Algorithms, M.Sc. thesis, Carleton University, May 1990.","DOI":"10.1145\/98524.98602"},{"key":"CR26","unstructured":"A. Knight and J.-R. Sack, Generating and Sorting Jordan Sequences, Technical Report SCS-TR-188, School of Computer Science, Carleton University, 1991."},{"key":"CR27","unstructured":"A. Knight and J.-R. Sack, Manuscript, Carleton University, 1991."},{"issue":"2","key":"CR28","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0734-189X(83)90065-8","volume":"22","author":"D. T. Lee","year":"1983","unstructured":"D. T. Lee, Visibility of a simple polygon,Comput. Vision Graphics Image Process.,22(2) (1983), 207?221.","journal-title":"Comput. Vision Graphics Image Process."},{"key":"CR29","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0020-0190(87)90086-X","volume":"25","author":"A. A. Melkman","year":"1987","unstructured":"A. A. Melkman, On-line construction of the convex hull of a simple polygon,Inform. Process. Lett.,25 (1987), 11?12.","journal-title":"Inform. Process. Lett."},{"key":"CR30","volume-title":"Technical Report A 04\/89, FB10","author":"K. Mehlhorn","year":"1989","unstructured":"K. Mehlhorn and S. N\u00e4her: LEDA, a Library of Efficient Data Types and Algorithms, Technical Report A 04\/89, FB10, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, 1989."},{"issue":"2","key":"CR31","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/S0734-189X(87)80169-X","volume":"39","author":"J. O'Rourke","year":"1987","unstructured":"J. O'Rourke, H. Booth, and R. Washington, Connect-the-dots: a new heuristic,Comput. Vision Graphics Image Process.,39(2), (1987), 258?266.","journal-title":"Comput. Vision Graphics Image Process."},{"key":"CR32","unstructured":"J. O'Rourke and M. Virmani, Generating Random Polygons, Smith Technical Report 11, August 1991."},{"issue":"3","key":"CR33","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1137\/0210035","volume":"10","author":"F. P. Preparata","year":"1981","unstructured":"F. P. Preparata, A new approach to planar point location,SIAM J. Comput.,10(3) (1981), 473?482.","journal-title":"SIAM J. Comput."},{"key":"CR34","volume-title":"Texts and Monographs in Computer Science","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. ShamosComputational Geometry: An Introduction, Texts and Monographs in Computer Science (D. Gries, (ed.), Springer-Verlag, New York, 1985."},{"key":"CR35","volume-title":"Ph.D. thesis","author":"J.-R. Sack","year":"1984","unstructured":"J.-R. Sack, Rectilinear Computational Geometry, Ph.D. thesis, McGill University, Montr\u00e9al, 1984; Technical Report SCS-TR 54, School of Computer Science, Carleton University, 1984."},{"key":"CR36","unstructured":"Peter Schorn, An object oriented workbench for experimental geometric computation,Proc. 2nd Canadian Conference in Computational Geometry, Ottawa, August 6?10, 1990, pp. 172?175."},{"key":"CR37","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach,32 (1985), 652?686.","journal-title":"J. Assoc. Comput. Mach"},{"key":"CR38","unstructured":"S. Suri, Minimum Link Paths in Polygons and Related Problems, Ph.D. thesis, The Johns Hopkins University, 1987."},{"issue":"1","key":"CR39","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R. E. Tarjan","year":"1988","unstructured":"R. E. Tarjan and C. J. van Wyk, An O(n log log n)-time algorithm for triangulating a simple polygon,SIAM J. Comput.,17(1) (1988), 143?178.","journal-title":"SIAM J. Comput."},{"key":"CR40","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0020-0190(85)90044-4","volume":"20","author":"E. Welzl","year":"1985","unstructured":"E. Welzl, Constructing the visibility graph ofn line segmens in O(n2) time,Inform. Process. Lett.,20 (1985), 167?171.","journal-title":"Inform. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187021.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01187021\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T06:56:53Z","timestamp":1683010613000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01187021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["BF01187021"],"URL":"https:\/\/doi.org\/10.1007\/bf01187021","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}