{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:39Z","timestamp":1725663399199},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_171","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:38:46Z","timestamp":1330191526000},"page":"649-660","source":"Crossref","is-referenced-by-count":0,"title":["Computing shortest transversals"],"prefix":"10.1007","author":[{"given":"Binay","family":"Bhattacharya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Godfried","family":"Toussaint","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"51_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(87)90226-2","volume":"25","author":"M. J. Atallah","year":"1987","unstructured":"Atallah, M. J. and Bajaj, C., \u201cEfficient algorithms for common transversals,\u201d Information Processing Letters, vol. 25, May 1987, pp.87\u201391.","journal-title":"Information Processing Letters"},{"key":"51_CR2","doi-asserted-by":"crossref","unstructured":"Avis, D. and Doskas, M., \u201cAlgorithms for high dimensional stabbing problems,\u201d Discrete and Applied Mathematics, to appear in 1990.","DOI":"10.1016\/0166-218X(90)90127-X"},{"key":"51_CR3","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/BF01952419","volume":"2","author":"D. Avis","year":"1986","unstructured":"Avis, D., Gum, T., and Toussaint, G. T., \u201cVisibility between two edges of a simple polygon,\u201d The Visual Computer, vol. 2, 1986, pp. 342\u2013357.","journal-title":"The Visual Computer"},{"key":"51_CR4","unstructured":"Aho, A. V., Hopcroft, J. E., & Ullman, J. D., Data Structures and Algorithms, Addison-Wesley, 1983."},{"key":"51_CR5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(86)90010-6","volume":"7","author":"M. J. Atallah","year":"1986","unstructured":"Atallah, M. J., \u201cComputing the convex hull of line intersections,\u201d Journal of Algorithms, vol. 7, 1986, pp.285\u2013288.","journal-title":"Journal of Algorithms"},{"issue":"12","key":"51_CR6","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1109\/TC.1981.1675729","volume":"C-30","author":"A. Avis","year":"1981","unstructured":"Avis, A. and Toussaint, G. T., \u201cAn optimal algorithm for determining the visibility of a polygon from an edge,\u201d IEEE Transactions on Computers, vol. C-30, No. 12, December 1981, pp.910\u2013914.","journal-title":"IEEE Transactions on Computers"},{"key":"51_CR7","doi-asserted-by":"crossref","unstructured":"Avis, D. and Wenger, R., \u201cAlgorithms for line stabbers in space,\u201d Proc. 3rd ACM Symposium on Computational Geometry, 1987, pp.300\u2013307.","DOI":"10.1145\/41958.41990"},{"issue":"3","key":"51_CR8","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF02187911","volume":"3","author":"D. Avis","year":"1988","unstructured":"Avis, D. and Wenger, R., \u201cPolyhedral line transversals in space,\u201d Discrete and Computational Geometry, vol. 3, No. 3, 1988, pp. 257\u2013266.","journal-title":"Discrete and Computational Geometry"},{"key":"51_CR9","unstructured":"Bhattacharya, B. K., Egyed, P., & Toussaint, G. T., \u201cComputing the wingspan of a butterfly,\u201d manuscript in preparation."},{"key":"51_CR10","doi-asserted-by":"crossref","unstructured":"Bhattacharya, B. K., Kirkpatrick, D. G., & Toussaint, G. T., \u201cDetermining sector visibility of a polygon,\u201d Proc. 5th ACM Symposium on Computational Geometry, Saarbruchen, 1989, pp.247\u2013254.","DOI":"10.1145\/73833.73861"},{"key":"51_CR11","unstructured":"Bajaj, C. and Li, M., \u201cOn the duality of intersection and closest points,\u201d Proc. 21st Allerton Conference, 1983, pp.459\u2013461."},{"key":"51_CR12","doi-asserted-by":"crossref","first-page":"333","DOI":"10.2140\/pjm.1976.64.333","volume":"64","author":"E. Buchman","year":"1976","unstructured":"Buchman, E. and Valentine, F. A., \u201cExternal visibility,\u201d Pacific Journal of Mathematics, vol. 64, 1976, pp. 333\u2013340.","journal-title":"Pacific Journal of Mathematics"},{"key":"51_CR13","doi-asserted-by":"crossref","unstructured":"Chazelle, B. M. and Dobkin, D. P., \u201cDetection is easier than computation,\u201d Proc. 12th Annual ACM Symposium on the Theory of Computing, 1980, pp. 146\u2013153.","DOI":"10.1145\/800141.804662"},{"key":"51_CR14","doi-asserted-by":"crossref","unstructured":"Chazelle, B. M. and Edelsbrunner, H., \u201cAn optimal algorithm for intersecting line segments in the plane,\u201d 29th Annual Symposium on Foundations of Computer Science, October 1988, pp. 590\u2013600.","DOI":"10.1109\/SFCS.1988.21975"},{"key":"51_CR15","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1080\/0025570X.1971.11976102","volume":"44","author":"G. D. Chakerian","year":"1971","unstructured":"Chakerian, G. D. and Lange, L. H., \u201cGeometric extremum problems,\u201d Mathematics Magazine, vol. 44, 1971, pp. 57\u201369.","journal-title":"Mathematics Magazine"},{"key":"51_CR16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0031-3203(85)90050-0","volume":"18","author":"Y. T. Ching","year":"1985","unstructured":"Ching, Y. T. and Lee, D. T., \u201cFinding the diameter of a set of lines,\u201d Pattern Recognition, vol. 18, 1985, pp. 249\u2013255.","journal-title":"Pattern Recognition"},{"key":"51_CR17","first-page":"408","volume-title":"Proc. Foundations of Computer Science","author":"J. S. Chang","year":"1984","unstructured":"Chang, J. S. and Yap, C. K., \u201cA polynomial solution for potato-peeling and other polygon inclusion and enclosure problems,\u201d Proc. Foundations of Computer Science, West Palm Beach, Fla., 1984, pp. 408\u2013416."},{"key":"51_CR18","unstructured":"DePano, N. A. A., and Aggarwal, A., \u201cFinding restricted k-envelopes for convex polygons,\u201d Proc. 22nd Allerton Conference, Urbana, Ill., 1984, pp. 81\u201390."},{"key":"51_CR19","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0304-3975(82)90120-7","volume":"27","author":"D. P. Dobkin","year":"1983","unstructured":"Dobkin, D. P. and Kirkpatrick, D. G., \u201cFast detection of polyhedral intersection,\u201d Theoretical Computer Science, vol. 27, 1983, pp. 241\u2013253.","journal-title":"Theoretical Computer Science"},{"key":"51_CR20","unstructured":"Devroye, L. and Toussaint, G. T., \u201cConvex hulls for random lines,\u201d Tech. Rept. SOCS-90.11, School of Computer Science, McGrill University, May 1990."},{"issue":"1","key":"51_CR21","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M. E. Dyer","year":"1984","unstructured":"Dyer, M. E., \u201cLinear time algorithms for two-and three-variable linear programs,\u201d SIAM Journal of Computing, Vol. 13, No. 1, February 1984, pp. 31\u201345.","journal-title":"SIAM Journal of Computing"},{"key":"51_CR22","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(85)90005-2","volume":"35","author":"H. Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H., \u201cFinding transversals for sets of simple geometric figures,\u201d Theoretical Computer Science, vol. 35, 1985, pp.55\u201369.","journal-title":"Theoretical Computer Science"},{"key":"51_CR23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0196-6774(85)90039-2","volume":"6","author":"H. Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H., \u201cComputing the extreme distances between two convex polygons,\u201d Journal of Algorithms, vol. 6, 1985, pp. 213\u2013224.","journal-title":"Journal of Algorithms"},{"key":"51_CR24","unstructured":"Edelsbrunner, H., Overmars, M. H., and Wood, D., \u201cGraphics in flatland: a case study,\u201d Tech. Report F79, Technical University of Graz, 1981."},{"key":"51_CR25","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/BF01934440","volume":"22.","author":"H. Edelsbrunner","year":"1982","unstructured":"Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D., \u201cStabbing line segments,\u201d BIT, vol. 22., 1982, pp.274\u2013281.","journal-title":"BIT"},{"key":"51_CR26","unstructured":"ElGindy, H. and Toussaint, G. T., \u201cEfficient algorithms for inserting and deleting edges from triangulations,\u201d Proc. Intl. Conf. on Foundations of Data Organization, Kyoto, Japan, May 1985."},{"key":"51_CR27","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF01898631","volume":"9","author":"B. Grunbaum","year":"1958","unstructured":"Grunbaum, B., \u201cOn common transversals,\u201d Arch. Math., vol. 9, 1958, pp. 465\u2013469.","journal-title":"Arch. Math."},{"key":"51_CR28","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J. Hershberger","year":"1989","unstructured":"Hershberger, J., \u201cFinding the upper envelope of n line segments in O(n log n) time,\u201d Information Processing Letters, vol. 33, 1989, pp. 169\u2013174.","journal-title":"Information Processing Letters"},{"key":"51_CR29","unstructured":"Houle, M. and Maciel, A., \u201cFinding the widest empty corridor through a set of points,\u201d in Snapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University, June 1988, pp. 201\u2013214."},{"key":"51_CR30","unstructured":"Houle, M., \u201cA measure of separability for point sets,\u201d in Snapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University, June 1988, pp. 21\u201336."},{"key":"51_CR31","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1215\/S0012-7094-49-01613-0","volume":"16","author":"A. Horn","year":"1949","unstructured":"Horn, A. and Valentine, F. A., \u201cSome properties of L-sets in the plane,\u201d Duke Mathematics Journal, vol.16, 1949, pp.131\u2013140.","journal-title":"Duke Mathematics Journal"},{"key":"51_CR32","doi-asserted-by":"crossref","unstructured":"Kazarinoff, N. D., Geometric Inequalities, Published by the Mathematical Association of America, 1961.","DOI":"10.5948\/UPO9780883859223"},{"key":"51_CR33","unstructured":"Ke, Y., \u201cDetecting the weak visibility of a simple polygon and related problems,\u201d The Johns Hopkins University, manuscript, March 1988."},{"issue":"1","key":"51_CR34","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. G. Kirkpatrick","year":"1986","unstructured":"Kirkpatrick, D. G. and Seidel, R., \u201cThe ultimate planar convex hull algorithm?\u201d SIAM Journal on Computing, vol. 15, No. 1, February 1986, pp. 287\u2013299.","journal-title":"SIAM Journal on Computing"},{"key":"51_CR35","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(85)90005-7","volume":"6","author":"V. Klee","year":"1985","unstructured":"Klee, V. and Laskowski, M. C., \u201cFinding the smallest triangles containing a given convex polygon,\u201d Journal of Algorithms, vol. 6, 1985, pp. 359\u2013375.","journal-title":"Journal of Algorithms"},{"key":"51_CR36","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/3029501","volume":"32","author":"L. H. Lange","year":"1959","unstructured":"Lange, L. H., \u201cCutting certain minimal corners,\u201d Mathematics Magazine, vol. 32, 1959, pp. 157\u2013160.","journal-title":"Mathematics Magazine"},{"key":"51_CR37","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF00181561","volume":"9","author":"T. Lewis","year":"1980","unstructured":"Lewis, T., \u201cTwo counterexamples concerning transversals for convex subsets of the plane,\u201d Geometriae Dedicata, vol. 9, 1980, pp.461\u2013465.","journal-title":"Geometriae Dedicata"},{"key":"51_CR38","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N., \u201cLinear-time algorithms for linear programming in R3 and related problems,\u201d SIAM Journal on Computing, Vol. 12, 1983, pp. 759\u2013776.","journal-title":"SIAM Journal on Computing"},{"key":"51_CR39","doi-asserted-by":"crossref","unstructured":"Niven, I., Maxima and Minima Without Calculus, Published by the Mathematical Association of America, 1981.","DOI":"10.1090\/dol\/006"},{"key":"51_CR40","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/0196-6774(86)90007-6","volume":"7","author":"J. O'Rourke","year":"1986","unstructured":"O'Rourke, J., Aggarwal, A., Maddila, S. and Baldwin, M., \u201cAn optimal algorithm for finding minimal enclosing triangles,\u201d Journal of Algorithms, vol. 7, 1986, pp. 258\u2013269.","journal-title":"Journal of Algorithms"},{"key":"51_CR41","unstructured":"O'Rourke, J., Art Gallery Theorems and Algorithms, Oxford University Press, 1987."},{"issue":"9","key":"51_CR42","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1145\/358746.358758","volume":"24","author":"J. O'Rourke","year":"1981","unstructured":"O'Rourke, J., \u201cAn on-line algorithm for fitting straight lines between data ranges,\u201d Communications of the ACM, vol. 24, No. 9, September 1981, pp.574\u2013578.","journal-title":"Communications of the ACM"},{"key":"51_CR43","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. Overmars","year":"1981","unstructured":"Overmars, M. and van Leeuwen, H., \u201cMaintenance of configurations in the plane,\u201d Journal of Computer & System Sciences, vol. 23, 1981, pp. 166\u2013204.","journal-title":"Journal of Computer & System Sciences"},{"key":"51_CR44","unstructured":"Robert, J.-M., \u201cStabbing hyperspheres by a hyperplane,\u201d in Snapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Rep. SOCS-88.11, Computational Geometry Lab., McGill University, June 1988, pp. 181\u2013188."},{"key":"51_CR45","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0020-0190(86)90045-1","volume":"23","author":"H. Rohnert","year":"1986","unstructured":"Rohnert, H., \u201cShortest paths in the plane with convex polygonal obstacles,\u201d Information Processing Letters, vol. 23, August 1986, pp. 71\u201386.","journal-title":"Information Processing Letters"},{"key":"51_CR46","doi-asserted-by":"crossref","unstructured":"Shamos, M. I. and Hoey, D., \u201cGeometric intersection problems,\u201d Seventeenth Annual IEEE Symposium on the Foundations of Computer Science, October 1976, pp. 208\u2013215.","DOI":"10.1109\/SFCS.1976.16"},{"key":"51_CR47","doi-asserted-by":"crossref","unstructured":"Sharir, M., \u201cThe shortest watchtower and related problems for polyhedral terrains,\u201d Information Processing Letters, in press.","DOI":"10.1016\/0020-0190(88)90120-2"},{"key":"51_CR48","volume-title":"An optimal algorithm for detecting weak visibility of a polygon","author":"J.-R. Sack","year":"1986","unstructured":"Sack, J.-R. and Suri, S., \u201cAn optimal algorithm for detecting weak visibility of a polygon,\u201d Tech. Rept. SCS-TR-114, Carleton University, Ottawa, Dec. 1986."},{"key":"51_CR49","unstructured":"Shermer, T. and Toussaint, G. T., \u201cCharacterizations of convex and star-shaped polygons,\u201d in Snapshots of Computational and Discrete Geometry, G. Toussaint, ed., Rept. SOCS-88.11, School of Computer Science, McGill Univ., June 1988."},{"key":"51_CR50","unstructured":"Teichman, M., \u201cShoving a table into a corner,\u201d in Snapshots of Computational and Discrete Geometry, G. T. Toussaint, ed., Tech. Report SOCS-88.11, Computational Geometry Laboratory, McGill University, June 1988, pp. 99\u2013118."},{"key":"51_CR51","unstructured":"Toussaint, G. T., \u201cSolving geometric problems with the rotating calipers,\u201d Proc. MELECON'83, Athens, Greece, 1983."},{"key":"51_CR52","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1090\/S0002-9939-1953-0058996-7","volume":"4","author":"F. A. Valentine","year":"1953","unstructured":"Valentine, F. A., \u201cMinimal sets of visibility,\u201d Proc. American Mathematical Society, vol. 4, 1953, pp. 917\u2013921.","journal-title":"Proc. American Mathematical Society"},{"key":"51_CR53","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1080\/00029890.1970.11992438","volume":"77","author":"F. A. Valentine","year":"1970","unstructured":"Valentine, F. A., \u201cVisible shorelines,\u201d American Mathematical Monthly, vol. 77, 1970. pp. 146\u2013152.","journal-title":"American Mathematical Monthly"},{"key":"51_CR54","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1080\/00029890.1976.11994073","volume":"83","author":"N. R. Wagner","year":"1976","unstructured":"Wagner, N. R., \u201cThe sofa problem,\u201d American Mathematical Monthly, vol. 83, 1976, pp. 188\u2013189.","journal-title":"American Mathematical Monthly"},{"key":"51_CR55","unstructured":"Wenger, R., \u201cStabbing and separation,\u201d Ph.D. thesis, School of Computer Science, McGill University, February 1988."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_171.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T22:42:18Z","timestamp":1640904138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_171","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}