Computing the external geodesic diameter of a simple polygon | Zendy

Dr Rajeev Samuel | Zendy; Godfried T. Toussaint | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Computing the external geodesic diameter of a simple polygon

Author(s) -

Dr Rajeev Samuel,

Godfried T. Toussaint

Publication year - 1990

Publication title -

computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.409

H-Index - 60

eISSN - 1436-5057

pISSN - 0010-485X

DOI - 10.1007/bf02247961

Subject(s) - geodesic , simple polygon , combinatorics , mathematics , polygon (computer graphics) , path (computing) , simple (philosophy) , shortest path problem , boundary (topology) , space (punctuation) , algorithm , regular polygon , geometry , computer science , mathematical analysis , telecommunications , philosophy , graph , programming language , operating system , epistemology , frame (networking)

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(n2) 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research