Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into smallsize pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the “size” of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.
Cutting Polygons into Small Pieces with Chords: LaserBased Localization
Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into smallsize pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the "size" of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.
 Publication Date:
 NSFPAR ID:
 10194795
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 173
 Page Range or eLocationID:
 7:17:23
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A=(α0,…,αn−1) , αi∈(−π,π) , for i∈{0,…,n−1} . The problem of realizing A by a polygon can be seen as that of constructing a straightline drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P⊂R2 realizing A has at least c crossings, for every c∈N , and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P⊂R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P⊂R3 , and for every realizable sequence the algorithm finds a realization.

We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A = (α0 , . . . , αn−1 ), αi ∈ (−π,π), for i ∈ {0,...,n − 1}. The problem of realizing A by a polygon can be seen as that of constructing a straightline drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P ⊂ R2 realizing A has at least c crossings, and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P ⊂ R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P ⊂ R3, and for every realizable sequence finds a realization.

We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are ``compact'' and ``contiguous,'' to use the terms referred to in most US state constitutions and/or US Supreme Court rulings. We study a method that outputs a solution in which each district is the intersection of a convex polygon with the geographical area. The average number of sides per polygon is less than six. The polygons tend to be quite compact. Every two districts differ in population by at most one (so we call the solution balanced). In fact, the solution is a centroidal power diagram: each polygon has an associated center in ℝ³ such that * the projection of the center onto the plane z = 0 is the centroid of the locations of people assigned to the polygon, and * for each person assigned to that polygon, the polygon's center is closest among all centers. The polygons are convex because they are the intersections of 3D Voronoi cells with the plane. Themore »

We present approximation and exact algorithms for piecewise regression of univariate and bivariate data using fixeddegree polynomials. Specifically, given a set S of n data points (x1, y1), . . . , (xn, yn) ∈ Rd × R where d ∈ {1, 2}, the goal is to segment xi’s into some (arbitrary) number of disjoint pieces P1, . . . , Pk, where each piece Pj is associated with a fixeddegree polynomial fj : Rd → R, to minimize the total loss function λk+ni=1(yi −f(xi))2, where λ ≥ 0 is a regularization term that penalizes model complexity (number of pieces) and f : kj=1 Pj → R is the piecewise polynomial function defined as fPj = fj. The pieces P1,...,Pk are disjoint intervals of R in the case of univariate data and disjoint axisaligned rectangles in the case of bivariate data. Our error approximation allows use of any fixeddegree polynomial, not just linear functions. Our main results are the following. For univariate data, we present a (1 + ε)approximation algorithm with time complexity O(nε log1ε), assuming that data is presented in sorted order of xi’s. For bivariate data, we √ present three results: a subexponential exact algorithm with running timemore »