Covering points with minimum/maximum area orthogonally convex polygons

---

Atıf İçin Kopyala

Evrendilek C., GENÇ B., Hnich B.

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, cilt.54, ss.32-44, 2016 (SCI-Expanded)

• Yayın Türü: Makale / Tam Makale
• Cilt numarası: 54
• Basım Tarihi: 2016
• Doi Numarası: 10.1016/j.comgeo.2016.02.003
• Dergi Adı: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
• Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
• Sayfa Sayıları: ss.32-44
• Hacettepe Üniversitesi Adresli: Evet

Özet

In this paper, we address the problem of covering a given set of points on the plane with minimum and/or maximum area orthogonally convex polygons. It is known that the number of possible orthogonally convex polygon covers can be exponential in the number of input points. We propose, for the first time, an O(n(2)) algorithm to construct either the maximum or the minimum area orthogonally convex polygon if it exists, else report the non-existence in O (n log n). (C) 2016 Elsevier B.V. All rights reserved.