TY - JOUR
T1 - On the multimodality of distances in convex polygons
AU - Avis, David
AU - Toussaint, Godfried T.
AU - Bhattacharya, Binay K.
N1 - Funding Information:
‘iResearch supported by N.S.E.R.C. Grants Nos. A-3013 and A-9293, and F.C.A.C. Grant No. EQ-1678.
PY - 1982
Y1 - 1982
N2 - Examples are given of n vertex convex polygons for which the distances between a fixed vertex and the remaining vertices, visited in order, form a multi-modal function. We show that this function may have as many as n/2 modes, or local maxima. Further examples are given of n vertex convex polygons in which n2/8 pairs of vertices are local maxima of their corresponding distance functions. These results are used to construct an example that shows that a general algorithm of Dobkin and Snyder may not, in fact, be used to find the diameter of a convex polygon.
AB - Examples are given of n vertex convex polygons for which the distances between a fixed vertex and the remaining vertices, visited in order, form a multi-modal function. We show that this function may have as many as n/2 modes, or local maxima. Further examples are given of n vertex convex polygons in which n2/8 pairs of vertices are local maxima of their corresponding distance functions. These results are used to construct an example that shows that a general algorithm of Dobkin and Snyder may not, in fact, be used to find the diameter of a convex polygon.
UR - http://www.scopus.com/inward/record.url?scp=49049144884&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=49049144884&partnerID=8YFLogxK
U2 - 10.1016/0898-1221(82)90054-2
DO - 10.1016/0898-1221(82)90054-2
M3 - Article
AN - SCOPUS:49049144884
SN - 0898-1221
VL - 8
SP - 153
EP - 156
JO - Computers and Mathematics with Applications
JF - Computers and Mathematics with Applications
IS - 2
ER -