Computing the extreme distances between two convex polygons Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 A polygon in the plane is convex if it contains all line segments connecting any two of its points. Let P and Q denote two convex polygons. The computational complexity of finding the minimum and maximum distance possible between two points p in P and q in Q is studied. An algorithm is described that determines the minimum distance (together with points p and q that realize it) in O(logm + logn) time, where m and n denote the number of vertices of P and Q, respectively. This is optimal in the worst case. For computing the maximum distance, a lower bound Ω(m + n) is proved. This bound is also shown to be best possible by establishing an upper bound of O(m + n). Academic Press 1985 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4115 Edelsbrunner H. Computing the extreme distances between two convex polygons. <i>Journal of Algorithms</i>. 1985;6(2):213-224. doi:<a href="https://doi.org/10.1016/0196-6774(85)90039-2">10.1016/0196-6774(85)90039-2</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/0196-6774(85)90039-2 info:eu-repo/semantics/altIdentifier/issn/0196-6774 info:eu-repo/semantics/altIdentifier/e-issn/1090-2678 info:eu-repo/semantics/closedAccess