caa a22 4500 465751237 CHVBK 20180323111834.0 cr unu---uuuuu 170327e19900301xx s 000 0 eng 10.1007/BF02247961 doi (NATIONALLICENCE)springer-10.1007/BF02247961 Computing the external geodesic diameter of a simple polygon [Elektronische Daten] [D. Samuel, G. Toussaint] Die Berechnung des äußeren geodätischen Durchmessers eines einfachen Vielecks Given a simple polygonP ofn vertices, we present an algorithm that finds the pair of points on the boundary ofP that maximizes theexternal shortest path between them. This path is defined as theexternal geodesic diameter ofP. The algorithm takes0(n 2) time and requires0(n) space. Surprisingly, this problem is quite different from that of computing theinternal geodesic diameter ofP. While the internal diameter is determined by a pair of vertices ofP, this is not the case for the external diameter. Finally, we show how this algorithm can be extended to solve theall external geodesic furthest neighbours problem. Springer-Verlag, 1990 Polygon nationallicence geodesics nationallicence diameter nationallicence furthest neighbour nationallicence algorithm nationallicence complexity nationallicence computational geometry nationallicence Samuel D. School of Computer Science, McGill University, McConnell Engineering Building 3480 University Street, H3A 2A7, Montréal, Canada aut Toussaint G. School of Computer Science, McGill University, McConnell Engineering Building 3480 University Street, H3A 2A7, Montréal, Canada aut Computing Springer-Verlag 44/1(1990-03-01), 1-19 0010-485X 44:1<1 1990 44 607 https://doi.org/10.1007/BF02247961 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02247961 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Samuel D. School of Computer Science, McGill University, McConnell Engineering Building 3480 University Street, H3A 2A7, Montréal, Canada aut NATIONALLICENCE 700 1- Toussaint G. School of Computer Science, McGill University, McConnell Engineering Building 3480 University Street, H3A 2A7, Montréal, Canada aut NATIONALLICENCE 773 0- Computing Springer-Verlag 44/1(1990-03-01), 1-19 0010-485X 44:1<1 1990 44 607 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer