View in EDS HTML Full Text PDF Full Text

Algorithms for Halfplane Coverage and Related Problems.

Saved in:
Bibliographic Details
Title: Algorithms for Halfplane Coverage and Related Problems.
Authors: Wang, Haitao1 (AUTHOR) haitao.wang@utah.edu, Xue, Jie2 (AUTHOR) jiexue@nyu.edu
Source: Discrete & Computational Geometry. Jun2026, Vol. 75 Issue 4, p1073-1104. 32p.
Subjects: Algorithms, Computational geometry, Geometric approach, Polygons, Mathematical optimization, Time complexity
Abstract: Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an O (n 4 / 3 log 5 / 3 n log O (1) log n) -time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of n 10 / 3 2 O (log ∗ n) time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O (n log n) time, which improves the previously best algorithm of n 4 / 3 2 O (log ∗ n) time and matches an Ω (n log n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O (n log n) time, which in turn leads to an O (n log n) -time algorithm for computing an instance-optimal ε -kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O (n k log n) -time algorithm for this problem in SoCG 2023, where k is the size of the ε -kernel; they also raised an open question whether the problem can be solved in O (n log n) time. Our result thus answers the open question affirmatively. [ABSTRACT FROM AUTHOR]
Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 194162856
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Algorithms for Halfplane Coverage and Related Problems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Wang%2C+Haitao%22">Wang, Haitao</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> haitao.wang@utah.edu</i><br /><searchLink fieldCode="AR" term="%22Xue%2C+Jie%22">Xue, Jie</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> jiexue@nyu.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Jun2026, Vol. 75 Issue 4, p1073-1104. 32p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+approach%22">Geometric approach</searchLink><br /><searchLink fieldCode="DE" term="%22Polygons%22">Polygons</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Time+complexity%22">Time complexity</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an O (n 4 / 3 log 5 / 3 n log O (1) log n) -time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of n 10 / 3 2 O (log ∗ n) time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O (n log n) time, which improves the previously best algorithm of n 4 / 3 2 O (log ∗ n) time and matches an Ω (n log n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O (n log n) time, which in turn leads to an O (n log n) -time algorithm for computing an instance-optimal ε -kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O (n k log n) -time algorithm for this problem in SoCG 2023, where k is the size of the ε -kernel; they also raised an open question whether the problem can be solved in O (n log n) time. Our result thus answers the open question affirmatively. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=194162856
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00454-024-00709-y
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 32
        StartPage: 1073
    Subjects:
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Computational geometry
        Type: general
      – SubjectFull: Geometric approach
        Type: general
      – SubjectFull: Polygons
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
      – SubjectFull: Time complexity
        Type: general
    Titles:
      – TitleFull: Algorithms for Halfplane Coverage and Related Problems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Wang, Haitao
      – PersonEntity:
          Name:
            NameFull: Xue, Jie
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 01795376
          Numbering:
            – Type: volume
              Value: 75
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Discrete & Computational Geometry
              Type: main
ResultId 1