{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:40:12Z","timestamp":1778294412110,"version":"3.51.4"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1986,12,1]],"date-time":"1986-12-01T00:00:00Z","timestamp":533779200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Visual Computer"],"published-print":{"date-parts":[[1986,12]]},"DOI":"10.1007\/bf01952419","type":"journal-article","created":{"date-parts":[[2005,7,28]],"date-time":"2005-07-28T08:24:41Z","timestamp":1122539081000},"page":"342-357","source":"Crossref","is-referenced-by-count":12,"title":["Visibility between two edges of a simple polygon"],"prefix":"10.1007","volume":"2","author":[{"given":"David","family":"Avis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Teren","family":"Gum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Godfried","family":"Toussaint","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01952419_CR1","unstructured":"Asano T (1985) Efficient algorithm for finding the visibility polygon for a polygonal region with holes. Tech Rep, Osaka Electro Communication University"},{"key":"BF01952419_CR2","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1109\/TIT.1983.1056600","volume":"29","author":"D Avis","year":"1983","unstructured":"Avis D, ElGindy H (1983) A combinatorial approach to polygon similarity. IEEE Trans Inf Theory. vol IT-29: 148\u2013150","journal-title":"IEEE Trans Inf Theory. vol IT"},{"key":"BF01952419_CR3","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1109\/TC.1981.1675729","volume":"30","author":"D Avis","year":"1981","unstructured":"Avis D, Toussaint GT (1981) An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Trans Comput (December 1986) C-30: 910\u2013914","journal-title":"IEEE Trans Comput (December 1986) C"},{"key":"BF01952419_CR4","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0209045","volume":"9","author":"MR Brown","year":"1980","unstructured":"Brown MR, Tarjan RE (1980) Design and analysis of a data structure for representing sorted lists. SIAM J Comput 9: 594\u2013614","journal-title":"SIAM J Comput"},{"key":"BF01952419_CR5","doi-asserted-by":"crossref","unstructured":"Chazelle B (1982) A theorem on polygon cutting with applications. 23rd Annual IEEE Symposium on Foundations of Computer Science, pp 339\u2013349","DOI":"10.1109\/SFCS.1982.58"},{"key":"BF01952419_CR6","unstructured":"Chu WH, Lee DT (1983) The hidden line elimination problem revisited. Proc Internat Conf on Advanced Automation, Taipei, Taiwan (December 1983), pp 469\u2013480"},{"key":"BF01952419_CR7","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chav\u00e1tal","year":"1975","unstructured":"Chav\u00e1tal V (1975) A Combinatorial theorem in plane geometry. J Comb Theory [Ser B] 18: 39\u201341","journal-title":"J Comb Theory [Ser B]"},{"key":"BF01952419_CR8","doi-asserted-by":"crossref","unstructured":"Chazelle B, Guibas LJ (1985) Visibility and intersection problems in plane geometry. Proc Symposium on Computational Geometry, Baltimore (June 1985) pp 135\u2013146","DOI":"10.1145\/323233.323252"},{"key":"BF01952419_CR9","unstructured":"Donald BR (1983) Hypothesizing channels through free-space in solving the findpath problem, Massachussetts Institute of Technology, Artificial Intelligence Laboratory (June 1983) A.I. Memo no. 738"},{"key":"BF01952419_CR10","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0146-664X(79)90076-5","volume":"11","author":"L Davis","year":"1979","unstructured":"Davis L, Benedikt M (1979) Computational models of space: Isovists and isovist fields. Comp Graphics and Image Proc. 11: 49\u201372","journal-title":"Comp Graphics and Image Proc"},{"key":"BF01952419_CR11","unstructured":"Edelsbrunner H (1983) Problem P 36. Bull. EATCS 21 (October 1983), pp 195"},{"key":"BF01952419_CR12","unstructured":"ElGindy H (1980) Visibility in polygons with applications. M Sc Thesis (November 1980) School of Computer Science, McGill University"},{"key":"BF01952419_CR13","unstructured":"ElGindy H (1985) Hierarchical decomposition of polygons with applications. Ph D Thesis May 1985, School of Computer Science, McGill University"},{"key":"BF01952419_CR14","first-page":"180","volume":"2","author":"H ElGindy","year":"1981","unstructured":"ElGindy H, Avis D (1981) A finear algorithm for computing the visibility polygon from a point J Algorithms 2: 180\u2013197","journal-title":"J Algorithms"},{"key":"BF01952419_CR15","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02263430","volume":"31","author":"H ElGindy","year":"1983","unstructured":"ElGindy H, Avis D, Toussaint GT (1983) Applications of a two-dimensional hidden-line algorithm to other geometric problems. Computing 31: 191\u2013202","journal-title":"Computing"},{"issue":"6","key":"BF01952419_CR16","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1109\/PGEC.1967.264724","volume":"16","author":"H Freeman","year":"1967","unstructured":"Freeman H, Loutrel PP (1967) An algorithm for the two-dimensional \u2018hiden line\u2019 problem\u201d. IEEE Trans Electronic Computers EC-16(6): 784\u2013790","journal-title":"IEEE Trans Electronic Computers EC"},{"issue":"3","key":"BF01952419_CR17","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0010-4485(78)90147-1","volume":"10","author":"JG Griffiths","year":"1978","unstructured":"Griffiths JG (1978) Bibliography of hidden-line and hidden-surface algorithms. Computer Aided Design 10(3): 203\u2013206","journal-title":"Computer Aided Design"},{"key":"BF01952419_CR18","doi-asserted-by":"crossref","unstructured":"Guibas L, Hershberger J, Leven D, Sharir M, Tarjan RE (1986) Linear time algorithm for visibility and shortest path problem inside simple polygon. Proc Symposium on Computational Geometry, Yorktown Heights, New York (June 1986)","DOI":"10.1145\/10515.10516"},{"key":"BF01952419_CR19","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"MR Garey","year":"1978","unstructured":"Garey MR, Johnson DS, Preparata FP, Tarjan RE (1978) Triangulating a simple polygon. Int Proc Lett 7: 175\u2013179","journal-title":"Int Proc Lett"},{"key":"BF01952419_CR20","doi-asserted-by":"crossref","unstructured":"Hightower DW (1969) A solution to line-routing problems on the continuous plane. Proc of Design Automation Workshop, pp 1\u201324","DOI":"10.1145\/800260.809014"},{"key":"BF01952419_CR21","first-page":"120","volume":"22","author":"K Hoffmann","year":"1984","unstructured":"Hoffmann K, Mehlhorn K (1984) Intersecting a line and a simple polygon. Bull EATCS 22 (February 1984), pp 120\u2013121","journal-title":"Bull EATCS"},{"key":"BF01952419_CR22","doi-asserted-by":"crossref","unstructured":"Hoffman K, Mehlhorn K, Rosenstiehl P, Tarjan RE (1985) Sorting Jordan sequences in linear time. Proc Symposium on Computational Geometry, Baltimore (June 1985) pp 196\u2013203","DOI":"10.1145\/323233.323259"},{"key":"BF01952419_CR23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S Huddleston","year":"1982","unstructured":"Huddleston S, Mehlhorn K (1982) A new data structure for representing sorted lists. Acta Inf 17: 157\u2013184","journal-title":"Acta Inf"},{"key":"BF01952419_CR24","volume-title":"The art of computer programming, vol III: Sorting and searching","author":"DE Knuth","year":"1973","unstructured":"Knuth DE (1973) The art of computer programming, vol III: Sorting and searching, Addison-Wesley, Reading, Mass"},{"key":"BF01952419_CR25","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0734-189X(83)90065-8","volume":"22","author":"DT Lee","year":"1983","unstructured":"Lee DT (1983) Visibility of a simple polygon. Comput Vision, Graphics and Imagae Processing 22 207\u2013221","journal-title":"Comput Vision, Graphics and Imagae Processing"},{"key":"BF01952419_CR26","unstructured":"Lee DT, Lin A (1984) Computing the visibility polygon from an edge. Tech Rep, Northwestern University"},{"issue":"3","key":"BF01952419_CR27","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1145\/322139.322142","volume":"26","author":"DT Lee","year":"1979","unstructured":"Lee DT, Preparata FP (1979) An optimal algorithm for finding the kernel of a polygon. J ACM 26(3): 415\u2013421","journal-title":"J ACM"},{"key":"BF01952419_CR28","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"DT Lee","year":"1984","unstructured":"Lee DT, Preparata FP (1984) Euclidean shortest paths in the presence of rectilinear barriers. Networks 14: 393\u2013410","journal-title":"Networks"},{"key":"BF01952419_CR29","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T Lozano-Perez","year":"1979","unstructured":"Lozano-Perez T, Wesley M (1979) An algorithm for planning collision-free paths among polyhedral obstacles. Commun ACM 22: 560\u2013570","journal-title":"Commun ACM"},{"key":"BF01952419_CR30","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(81)90101-0","volume":"12","author":"D Mater","year":"1981","unstructured":"Mater D, Salveter C (1981) Hysterical B-trees. Inf Proc Lett 12: 199\u2013202","journal-title":"Inf Proc Lett"},{"key":"BF01952419_CR31","doi-asserted-by":"crossref","unstructured":"Mehlhorn K (1984) Data structures and efficient algorithms, vol 1: Sorting and searching, Springer Verlag","DOI":"10.1007\/978-3-642-69672-5_2"},{"key":"BF01952419_CR32","series-title":"Tech Rep (April 1985) CS-85-260","volume-title":"On computing the visibility polygon from a point","author":"AA Melkman","year":"1985","unstructured":"Melkman AA (1985) On computing the visibility polygon from a point. Tech Rep (April 1985) CS-85-260, Ben Gurion University, Israel"},{"key":"BF01952419_CR33","doi-asserted-by":"crossref","unstructured":"Nilsson NJ (1969) A mobile automaton: An application of artificial intelligence techniques. Proc IJCAI-69, pp 509\u2013520","DOI":"10.21236\/ADA459660"},{"key":"BF01952419_CR34","doi-asserted-by":"crossref","unstructured":"Preparata FP, Shamos MI (1985) Computational geometry: An introduction. Springer-Verlag pp 160\u2013165","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"BF01952419_CR35","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/BF01890987","volume":"2","author":"D Rappaport","year":"1986","unstructured":"Rappaport D (1986) A linear algorithm for eliminating hidden line from a polygonal cyclinder. The Visual Computer, 2: 44\u201353","journal-title":"The Visual Computer"},{"key":"BF01952419_CR36","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0167-8655(85)90040-6","volume":"3","author":"D Rappaport","year":"1985","unstructured":"Rappaport D, Toussaint GT (1985) A simple linear hidden-line algorithm for star-shaped polygons. Pattern Recognition Lett 3: 35\u201339","journal-title":"Pattern Recognition Lett"},{"key":"BF01952419_CR37","unstructured":"Rohnert H (1985) Shortest paths in the plane with convex polygonal obstacles. Tech Rep A 85\/06, University of Saarbr\u00fckken"},{"key":"BF01952419_CR38","unstructured":"Shamos MI (1977) Problems in computational geometry. Carnegie Mellon University"},{"key":"BF01952419_CR39","unstructured":"Shapiro LG, Haralick RM (1980) Algorithms for inexact matching. Proc 5th Internat Conf on Pattern Recognition, Miami Beach, pp 202\u2013207"},{"key":"BF01952419_CR40","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1109\/TPAMI.1979.4766871","volume":"1","author":"LG Shapiro","year":"1979","unstructured":"Shapiro LG, Haralick RM (1979) Decomposition of two dimensional shapes by graph-theoretic clustering. IEEE Trans on Pattern Analysis and Machine Intelligence (January 1979) vol. PAMI-1, pp 10\u201320","journal-title":"IEEE Trans on Pattern Analysis and Machine Intelligence (January 1979) vol. PAMI"},{"key":"BF01952419_CR41","unstructured":"Suri S, O'Rourke J (1985) Worst-case optimal algorithms for constructing visibility polygons with holes. Tech Rep (August 1985) JHU\/EECS-1985\/12"},{"key":"BF01952419_CR42","unstructured":"Sack JR, Toussaint GT (1984) Translating polygons in the plane. Tech Rep SCS-TR-47 (March 1984) Carleton University"},{"key":"BF01952419_CR43","doi-asserted-by":"crossref","unstructured":"Stoer J, Witzgall C (1970) Convexity and optimization in finite dimensions I. Springer-Verlag","DOI":"10.1007\/978-3-642-46216-0"},{"key":"BF01952419_CR44","unstructured":"Toussaint GT (1980) Pattern recognition and geometrical complexity. Proc 5th Internat Conf on Pattern Recognition (December 1980) Miami Beach, FL"},{"key":"BF01952419_CR45","unstructured":"Toussaint GT (1983) Solving geometric problems with the rotating calipers. Proc MELECON '83, Athens, Greece"},{"key":"BF01952419_CR46","unstructured":"Toussaint GT (1985) Shortest path solves edge-to-edge visibility in a polygon. Tech Rep SOCS-85. 19 (September 1985) McGill University, also to appear in: Pattern recognition Lett"},{"key":"BF01952419_CR47","unstructured":"Toussaint GT (1985) Shortest path solves translation separability of polygons. Tech Rep SOCS-85.27. (October 1985) McGill University"},{"key":"BF01952419_CR48","unstructured":"Toussaint GT (1986) A linear time algorithm for solving the strong hidden-line problem in a simple polygon. Tech Rep SOCS-86.2 (January 1986) McGill University"},{"key":"BF01952419_CR49","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1017\/S0263574700008924","volume":"2","author":"GT Toussaint","year":"1984","unstructured":"Toussaint GT, ElGindy H (1984) Separation of two monotone polygons in linear time. Robotica 2:215\u2013220","journal-title":"Robotica"},{"key":"BF01952419_CR50","unstructured":"Toussaint GT, Sack J-R (1983) Some new results on moving polygons in the plane. Proc Robotic Intelligence and Productivity Conference, Detroit, pp 158\u2013163"},{"key":"BF01952419_CR51","doi-asserted-by":"crossref","unstructured":"Tarjan RE, Van Wyk C (1986) A linear time algorithm for triangulating simple polygons. Proc Eighteenth Annual ACM Symposium on Theory of Computing, pp 380\u2013388","DOI":"10.1145\/12130.12170"},{"key":"BF01952419_CR52","unstructured":"Tarjan RE, Van Wyk C (submitted) AnO(nloglogn)-time algorithm for triangulating simple polygons. SIAM J Comput"},{"key":"BF01952419_CR53","unstructured":"Yao FF (1983) On the priority approach to hidden surface algorithms. Proc 21st Annual Symposium on Foundations of Computer Science (October 1983), pp 301\u2013307"}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01952419.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01952419\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01952419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,28]],"date-time":"2024-01-28T05:26:02Z","timestamp":1706419562000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01952419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,12]]},"references-count":53,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1986,12]]}},"alternative-id":["BF01952419"],"URL":"https:\/\/doi.org\/10.1007\/bf01952419","relation":{},"ISSN":["0178-2789","1432-8726"],"issn-type":[{"value":"0178-2789","type":"print"},{"value":"1432-8726","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,12]]}}}