We study the problem of minimizing the diameter of a polygon in the plane by attaching a segment to the polygon. Both endpoints of the segment must lie on the boundary of the polygon, while its relative interior must be disjoint from the polygon. Such a segment is considered an addition to the polygon, and thus it (or part of it) can be used in geodesic paths connecting pairs of points in the union of the polygon and itself. This problem can be considered a geometric analogue to the problem of augmenting graphs by inserting edges to minimize the diameter. We present an O(n)-time algorithm to determine whether the diameter of an x-monotone polygon with n vertices can be reduced by attaching a horizontal segment to the polygon under the \(L_1\) metric. We also present an \(O(n\log n)\) -time algorithm using O(n) space for finding a horizontal segment that minimizes the diameter.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Shortcutting the Diameter of a Polygon

  • Taekang Eom,
  • Taehoon Ahn,
  • Minju Song,
  • Hee-Kap Ahn

摘要

We study the problem of minimizing the diameter of a polygon in the plane by attaching a segment to the polygon. Both endpoints of the segment must lie on the boundary of the polygon, while its relative interior must be disjoint from the polygon. Such a segment is considered an addition to the polygon, and thus it (or part of it) can be used in geodesic paths connecting pairs of points in the union of the polygon and itself. This problem can be considered a geometric analogue to the problem of augmenting graphs by inserting edges to minimize the diameter. We present an O(n)-time algorithm to determine whether the diameter of an x-monotone polygon with n vertices can be reduced by attaching a horizontal segment to the polygon under the \(L_1\) metric. We also present an \(O(n\log n)\) -time algorithm using O(n) space for finding a horizontal segment that minimizes the diameter.