Covering points with orthogonally convex polygons

Genc B., Evrendilek C., Hnich B.

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, cilt.44, sa.5, ss.249-264, 2011 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 44 Sayı: 5
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.comgeo.2010.12.001
  • Dergi Adı: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.249-264
  • Anahtar Kelimeler: Cover, Orthogonal, Polygon, Point, Reconstruction
  • Hacettepe Üniversitesi Adresli: Hayır

Özet

In this paper, we address the problem of covering points with orthogonally convex polygons. In particular, given a point set of size n on the plane, we aim at finding if there exists an orthogonally convex polygon such that each edge of the polygon covers exactly one point and each point is covered by exactly one edge. We show that if such a polygon exists, it may not be unique. We propose an O(n log n) algorithm to construct such a polygon if it exists, or else report the non-existence in the same time bound. We also extend our algorithm to count all such polygons without hindering the overall time complexity. Finally, we show how to construct all k such polygons in O(n log n + kn) time. All the proposed algorithms are fast and practical. (C) 2010 Elsevier B.V. All rights reserved.