This content will become publicly available on February 27, 2025
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 NPhard. In this paper, we consider two lineconstrained 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
 NSFPAR ID:
 10546357
 Publisher / Repository:
 World Scientific
 Date Published:
 Journal Name:
 International Journal of Computational Geometry & Applications
 ISSN:
 02181959
 Page Range / eLocation ID:
 1 to 23
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 kunion 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

This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle [Formula: see text] and height [Formula: see text]. The apex of each cone is restricted to lie on the ground plane. Its orientation angle (tilt) [Formula: see text] is the angle difference between the cone bisector and the ground plane normal. This is a novel variant of the 3D Traveling Salesman Problem with Neighborhoods (TSPN) called ConeTSPN. One application of ConeTSPN is to compute a trajectory to observe a given set of locations with a camera: for each location, we can generate a set of cones whose apex and orientation angles [Formula: see text] and [Formula: see text] correspond to the camera’s field of view and tilt. The height of each cone [Formula: see text] corresponds to the desired resolution. Recently, Plonski and Isler presented an approximation algorithm for ConeTSPN for the case where all cones have a uniform orientation angle of [Formula: see text]. We study a new variant of ConeTSPN where we relax this constraint and allow the cones to have nonuniform orientations. We call this problem Tilted ConeTSPN and present a polynomialtime approximation algorithm with ratio [Formula: see text], where [Formula: see text] is the set of all cone heights. We demonstrate through simulations that our algorithm can be implemented in a practical way and that by exploiting the structure of the cones we can achieve shorter tours. Finally, we present experimental results from various agriculture applications that show the benefit of considering view angles for path planning.

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 NPhard. In this paper, we consider a lineconstrained 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 unitdisk 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

null (Ed.)In this paper, we consider the distributed version of Support Vector Machine (SVM) under the coordinator model, where all input data (i.e., points in [Formula: see text] space) of SVM are arbitrarily distributed among [Formula: see text] nodes in some network with a coordinator which can communicate with all nodes. We investigate two variants of this problem, with and without outliers. For distributed SVM without outliers, we prove a lower bound on the communication complexity and give a distributed [Formula: see text]approximation algorithm to reach this lower bound, where [Formula: see text] is a user specified small constant. For distributed SVM with outliers, we present a [Formula: see text]approximation algorithm to explicitly remove the influence of outliers. Our algorithm is based on a deterministic distributed top [Formula: see text] selection algorithm with communication complexity of [Formula: see text] in the coordinator model.more » « less

Meier and Zupan proved that an orientable surface [Formula: see text] in [Formula: see text] admits a triplane 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 chdiagrams to triplane diagrams, finding the minimal bridge number for each surface in the table and providing upper bounds for the crossing numbers.more » « less