Covering points with orthogonal polygons

Evrendilek C., Genc B., Hnich B.

DISCRETE APPLIED MATHEMATICS, cilt.164, ss.92-99, 2014 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 164
  • Basım Tarihi: 2014
  • Doi Numarası: 10.1016/j.dam.2012.01.018
  • Dergi Adı: DISCRETE APPLIED MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.92-99
  • Hacettepe Üniversitesi Adresli: Hayır

Özet

We address the problem of covering points with orthogonal polygons. Specifically, given a set of n points in the plane, we investigate the existence of an orthogonal polygon such that there is a one-to-one correspondence between the points and the edges of the polygon. In an earlier paper, we have shown that constructing such a covering with an orthogonally convex polygon, if any, can be done in O(n log n) time. In case an orthogonally convex polygon cannot cover the point set, we show in this paper that the problem of deciding whether such a point set can be covered with any orthogonal polygon is NP-complete. The problem remains NP-complete even if the orientations of the edges covering each point are specified in advance as part of the input. (C) 2012 Elsevier B.V. All rights reserved.

We address the problem of covering points with orthogonal polygons. Specifically, given a set of n points in the plane, we investigate the existence of an orthogonal polygon such that there is a one-to-one correspondence between the points and the edges of the polygon. In an earlier paper, we have shown that constructing such a covering with an orthogonally convex   polygon, if any, can be done in O(nlogn) time. In case an orthogonally convex polygon cannot cover the point set, we show in this paper that the problem of deciding whether such a point set can be covered with any orthogonal polygon is NP-complete. The problem remains NP-complete even if the orientations of the edges covering each point are specified in advance as part of the input.