skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Algorithms for Covering Barrier Points by Mobile Sensors with Line Constraint
We study the problem of covering barrier points by mobile sensors. Each sensor is represented by a point in the plane with the same covering range [Formula: see text] so that any point within distance [Formula: see text] from the sensor can be covered by the sensor. Given a set [Formula: see text] of [Formula: see text] points (called “barrier points”) and a set [Formula: see text] of [Formula: see text] points (representing the “sensors”) in the plane, the problem is to move the sensors so that each barrier point is covered by at least one sensor and the maximum movement of all sensors is minimized. The problem is NP-hard. In this paper, we consider two line-constrained variations of the problem and present efficient algorithms that improve the previous work. In the first problem, all sensors are given on a line [Formula: see text] and are required to move on [Formula: see text] only while the barrier points can be anywhere in the plane. We propose an [Formula: see text] time algorithm for the problem. We also consider the weighted case where each sensor has a weight; we give an [Formula: see text] time algorithm for this case. In the second problem, all barrier points are on [Formula: see text] while all sensors are in the plane but are required to move onto [Formula: see text] to cover all barrier points. We also solve the weighted case in [Formula: see text] time.  more » « less
Award ID(s):
2300356
PAR ID:
10546357
Author(s) / Creator(s):
;
Publisher / Repository:
World Scientific
Date Published:
Journal Name:
International Journal of Computational Geometry & Applications
ISSN:
0218-1959
Page Range / eLocation ID:
1 to 23
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023))
    Given a set P of n weighted points and a set S of m disks in the plane, the hitting set problem is to compute a subset 𝑃′ of points of P such that each disk contains at least one point of 𝑃′ and the total weight of all points of 𝑃′ is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line ℓ. We present an 𝑂((𝑚+𝑛)log(𝑚+𝑛)+𝜅log𝑚) time algorithm for the problem, where 𝜅 is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to 𝑂((𝑛+𝑚)log(𝑚+𝑛)). In addition, we solve the problem in 𝑂((𝑚+𝑛)log(𝑚+𝑛)) time in the 𝐿∞ and 𝐿1 metrics, in which a disk is a square and a diamond, respectively. 
    more » « less
  2. ; ; ; (, INFORMS Journal on Computing)
    null (Ed.)
    Given an element set E of order n, a collection of subsets [Formula: see text], a cost c S on each set [Formula: see text], a covering requirement r e for each element [Formula: see text], and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection [Formula: see text] to fully cover at least k elements such that the cost of [Formula: see text] is as small as possible and element e is fully covered by [Formula: see text] if it belongs to at least r e sets of [Formula: see text]. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a [Formula: see text]-approximation algorithm for MinPSMC, in which [Formula: see text] is the maximum size of a set in S. And when [Formula: see text], we present a bicriteria algorithm fully covering at least [Formula: see text] elements with approximation ratio [Formula: see text], where [Formula: see text] is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself. 
    more » « less
  3. ; (, Journal of Hyperbolic Differential Equations)
    null (Ed.)
    Let [Formula: see text] be a convex function satisfying [Formula: see text], [Formula: see text] for [Formula: see text], and [Formula: see text]. Consider the unique entropy admissible (i.e. Kružkov) solution [Formula: see text] of the scalar, 1-d Cauchy problem [Formula: see text], [Formula: see text]. For compactly supported data [Formula: see text] with bounded [Formula: see text]-variation, we realize the solution [Formula: see text] as a limit of front-tracking approximations and show that the [Formula: see text]-variation of (the right continuous version of) [Formula: see text] is non-increasing in time. We also establish the natural time-continuity estimate [Formula: see text] for [Formula: see text], where [Formula: see text] depends on [Formula: see text]. Finally, according to a theorem of Goffman–Moran–Waterman, any regulated function of compact support has bounded [Formula: see text]-variation for some [Formula: see text]. As a corollary we thus have: if [Formula: see text] is a regulated function, so is [Formula: see text] for all [Formula: see text]. 
    more » « less
  4. ; ; ; ; ; ; ; ; ; ; et al (, Journal of Knot Theory and Its Ramifications)
    Meier and Zupan proved that an orientable surface [Formula: see text] in [Formula: see text] admits a tri-plane diagram with zero crossings if and only if [Formula: see text] is unknotted, so that the crossing number of [Formula: see text] is zero. We determine the minimal crossing numbers of nonorientable unknotted surfaces in [Formula: see text], proving that [Formula: see text], where [Formula: see text] denotes the connected sum of [Formula: see text] unknotted projective planes with normal Euler number [Formula: see text] and [Formula: see text] unknotted projective planes with normal Euler number [Formula: see text]. In addition, we convert Yoshikawa’s table of knotted surface ch-diagrams to tri-plane diagrams, finding the minimal bridge number for each surface in the table and providing upper bounds for the crossing numbers. 
    more » « less
  5. (, Fractals)
    We collect from several sources some of the most important results on the forward and backward limits of points under real and complex rational functions, and in particular real and complex Newton maps, in one variable and we provide numerical evidence that the dynamics of Newton maps [Formula: see text] associated to real polynomial maps [Formula: see text] with no complex roots has a complexity comparable with that of complex Newton maps in one variable. In particular such a map [Formula: see text] has no wandering domain, almost every point under [Formula: see text] is asymptotic to a fixed point and there is some non-empty open set of points whose [Formula: see text]-limit equals the set of non-regular points of the Julia set of [Formula: see text]. The first two points were proved by B. Barna in the real one-dimensional case. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email