{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T13:52:56Z","timestamp":1660312376530},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"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":[[1995,9]]},"DOI":"10.1007\/bf01206332","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T13:24:38Z","timestamp":1109337878000},"page":"261-289","source":"Crossref","is-referenced-by-count":9,"title":["Optimal parallel algorithms for rectilinear link-distance problems"],"prefix":"10.1007","volume":"14","author":[{"given":"A.","family":"Lingas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Maheshwari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. R.","family":"Sack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"L. G. Alexandrav, H. N Djidjev and J.-R. Sack, Finding a Central Link Segment of a Simple Polygon in O(n log n) Time, Technical Report No. SCS-TR-163, Carleton University, 1989."},{"key":"CR2","unstructured":"E. M. Arkin, J. S. B. Mitchell, and S. Suri, Link queries and polygon approximation,Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 269?279."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0925-7721(91)90010-C","volume":"1","author":"M. Berg de","year":"1991","unstructured":"M. de Berg, On rectilinear link distance,Computation Geometry: Theory and Applications,1 (1991), 13?34.","journal-title":"Computation Geometry: Theory and Applications"},{"key":"CR4","unstructured":"O. Berkman, B. Schieber; and U. Vishkin, Some Doubly Logarithmic Optimal Parallel Algorithms Based on Finding all Nearest Smaller Values, Technical Report UMIACS-TR-88-79, University of Maryland, 1988."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"V. Chandru, S. K. Ghosh, A. Maheshwari, V. T. Rajan, and S. Saluja,NC-algorithms for minimum link path and related problems,Journal of Algorithms (1995), to appear.","DOI":"10.1006\/jagm.1995.1033"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF02574703","volume":"4","author":"B. Chazelle","year":"1991","unstructured":"B. Chazelle, Triangulating a simply polygon in linear time,Discrete and Computational Geometry,4 (1991), 485?524.","journal-title":"Discrete and Computational Geometry"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, R. Cole, and R. E. Tarjan, Randomized parallel algorithms for trapezoidal decomposition,Proc. 7th ACM Symposium on Computational Geometry, 1991, pp. 152?161.","DOI":"10.1145\/109648.109665"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, S. Kapoor, and P. M. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(log n)2) time,Proc. 3rd ACM Symposium on Computation Geometry, 1987, pp. 251?257.","DOI":"10.1145\/41958.41985"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02187714","volume":"4","author":"P. J. Rezende de","year":"1989","unstructured":"P. J. de Rezende, D. T. Lee, and Y. F. Wu, Rectilinear shortest paths with rectangular barriers,Discrete and Computational Geometry,4 (1989), 41?53.","journal-title":"Discrete and Computational Geometry"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02293040","volume":"8","author":"H. N. Djidjev","year":"1992","unstructured":"H. N. Djidjev, A. Lingas, and J.-R. Sack, AnO(n logn) algorithm for computing the link center of a simple polygon,Discrete and Computational Geometry,8 (1992), 131?152.","journal-title":"Discrete and Computational Geometry"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","volume":"12","author":"S. K. Ghosh","year":"1991","unstructured":"S. K. Ghosh, Computing the visibility polygon from a convex set and related problems,Journal of Algorithms,12 (1991), 75?95.","journal-title":"Journal of Algorithms"},{"key":"CR12","series-title":"Lecture Notes in Computer Science, Vol. 621","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-55706-7_10","volume-title":"SWAT 92","author":"S. K. Ghosh","year":"1992","unstructured":"S. K. Ghosh and A. Maheshwari, Parallel algorithms for all minimum link paths and link center problems,SWAT 92, Lecture Notes in Computer Science, Vol. 621, Springer-Verlag, Berlin, 1992, pp. 106?117."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, Planar separators and parallel polygon triangulation,Proc. ACM Symposium on Theory of Computing, 1992, pp. 507?515.","DOI":"10.1145\/129712.129762"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, S. Shauck, and S. Guha, Parallel methods for visibility and shortest path problems in simple polygons,Proc. 6th ACM Symposium on Computational Geometry, 1990, pp. 73?82.","DOI":"10.1145\/98524.98539"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"J. Hershberger, Optimal parallel algorithms for triangulated simple polygons,Proc. 8th ACM Symposium on Computational Geometry, 1992, pp. 33?42.","DOI":"10.1145\/142675.142687"},{"key":"CR16","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e0J\u00e0","year":"1992","unstructured":"J. J\u00e0J\u00e0,An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1992."},{"key":"CR17","first-page":"869","volume-title":"Handbook of Theoretical Computer Science, Vol. 1","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and R. Vijaya Ramachandran, Parallel algorithms for shared-memory machines, inHandbook of Theoretical Computer Science, Vol. 1, J. van Leeuwen, ed. Elsevier, Amsterdam, 1990, pp. 869?941"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"Y, Ke, An efficient algorithm for link-distance problems,Proc. 5th ACM Symposium on Computational Geometry, 1989, pp. 69?78.","DOI":"10.1145\/73833.73841"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"R. Klein and A. Lingas, Manhattonian proximity in a simple polygon,Proc. 8th ACM Symposium on Computational Geometry, 1992, pp. 312?319.","DOI":"10.1145\/142675.142738"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02187913","volume":"3","author":"W. Lenhart","year":"1988","unstructured":"W. Lenhart, R. Pollack, J. -R. Sack, R. Seidel, M. Sharir, S. Suri, G. Toussaint, S. Whitesides, and C. Yap, Computing the link center of a simple polygon,Discrete and Computational Geometry,3 (1988), 281?293.","journal-title":"Discrete and Computational Geometry"},{"key":"CR21","series-title":"Link\u00f6ping Studies in Science and Technology","volume-title":"Ph.D. thesis","author":"C. Levcopoulos","year":"1986","unstructured":"C. Levcopoulos, On Approximation Behavior of the Greedy Triangulation, Ph.D. thesis, Link\u00f6ping Studies in Science and Technology No. 74, Link\u00f6ping University, Sweden, 1986."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/0166-218X(92)90011-X","volume":"40","author":"C. Levcopoulos","year":"1992","unstructured":"C. Levcopoulos and O. Petersson, Matching parenthesis in parallel,Discrete and Applied Mathematics,40 (1992), 423?431.","journal-title":"Discrete and Applied Mathematics"},{"key":"CR23","unstructured":"A. Lingas, A, Maheshwari, and J.-R. Sack, Optimal Parallel Algorithms for Rectilinear Link Distance Problems, Technical Report SCS-TR-213, School of Computer Science, Carleton University, 1992."},{"issue":"7","key":"CR24","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1109\/43.144850","volume":"11","author":"K. M. McDonald","year":"1992","unstructured":"K. M. McDonald and J. G. Peters, Smallest paths in simple rectilinear polygons,IEEE Transactions on Computer-Aided Design, 11(7) (1992), 864?875.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BFb0028267","volume-title":"Proc. 2nd Workshop on Algorithms and Data Structures","author":"B. J. Nilsson","year":"1991","unstructured":"B. J. Nilsson and S. Schuierer, An optimal algorithm for the rectilinear link center of a rectilinear polygon,Proc. 2nd Workshop on Algorithms and Data Structures, F. Dehne, J. -R. Sack, and N. Santoro, eds., Springer-Verlag, New York 1991, pp. 249?260."},{"key":"CR26","series-title":"Lecture Notes in Computer Science, Vol. 553","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/3-540-54891-2_15","volume-title":"Computational Geometry-Methods, Algorithms, and Applications","author":"B. J. Nilsson","year":"1991","unstructured":"B. J. Nilsson and S. Schuierer, Computing the rectilinear link diameter of a polygon, inComputational Geometry-Methods, Algorithms, and Applications, Lecture Notes in Computer Science, Vol. 553, H. Noltemeier and H. Bieri, eds., Springer-Verlag, Berlin, 1991, pp. 203?216."},{"key":"CR27","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O'Rourke","year":"1987","unstructured":"J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, Oxford, 1987."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1109\/JRA.1987.1087092","volume":"3","author":"J. H. Reif","year":"1987","unstructured":"J. H. Reif and J. A. Storer, Minimizing turns for discrete movement in the interior of a polygon,IEEE Journal of Robotics and Automation,3 (1987), 182?193.","journal-title":"IEEE Journal of Robotics and Automation"},{"key":"CR29","unstructured":"J. -R. Sack, Rectilinear Computational Geometry, Ph.D. thesis, McGill University, 1984."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin, On finding lowest common ancestors: simplification and parallelization,SIAM Journal on Computing,17 (1988), 1253?1262.","journal-title":"SIAM Journal on Computing"},{"key":"CR31","series-title":"Lecture Notes in Computer Science, Vol. 665","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1007\/3-540-56503-5_29","volume-title":"STACS'93","author":"S. Schuierer","year":"1993","unstructured":"S. Schuierer, Rectilinear path queries in a simple rectilinear polygon,STACS'93, Lecture Notes in Computer Science, Vol. 665, Springer-Verlag, Berlin, 1993, pp. 282?293."},{"key":"CR32","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","volume":"35","author":"S. Suri","year":"1986","unstructured":"S. Suri, A linear time algorithm for minimum link path inside a simple polygon,Computer Vision, Graphics and Image Processing,35 (1986), 99?110.","journal-title":"Computer Vision, Graphics and Image Processing"},{"key":"CR33","unstructured":"S. Suri, Minimum Link Paths in Polygons and Related Problems, Ph.D thesis, Johns Hopkins University, 1987."},{"key":"CR34","first-page":"220","volume":"39","author":"S. Suri","year":"1989","unstructured":"S. Suri, Computing furthest neighbors in simple polygons,Journal of Computer Science,39 (1989), 220?335.","journal-title":"Journal of Computer Science"},{"key":"CR35","doi-asserted-by":"crossref","unstructured":"R. Tamassia and J. S. Vitter, Optimal parallel algorithms for transitive closure and point location in planar structures,Proc. 1st ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 339?408.","DOI":"10.1145\/72935.72978"},{"key":"CR36","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1982","unstructured":"R. E. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm,SIAM Journal on Computing,14 (1982), 862?874.","journal-title":"SIAM Journal on Computing"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206332.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01206332\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T23:14:24Z","timestamp":1586128464000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01206332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF01206332"],"URL":"https:\/\/doi.org\/10.1007\/bf01206332","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}