More Like this

1. Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

   Arkin, Esther; Das, Rathish; Gao, Jie; Goswami, Mayank; Mitchell, Joseph; Polishchuk, Valentin; Toth, Csaba (January 2020, Annual European Symposium on Algorithms)

   Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size 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. 

   more » « less
2. Polygons with Prescribed Angles in 2D and 3D

   https://doi.org/10.1007/978-3-030-68766-3_11  

   Efrat, Alon; Fulek, Radoslav; Kobourov, Stephen; Toth, Csaba D. (February 2021, Graph Drawing and Network Visualization)

   null (Ed.)

   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 straight-line 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. 

   more » « less
3. Polygons with Prescribed Angles in 2D and 3D

   Efrat, A; Fulek, R; Kobourov, S; Toth, C (October 2020, 28th International Symposium on Graph Drawing and Network Visualization (GD))

   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 straight-line 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. 

   more » « less
4. Maximal Simplification of Polyhedral Reductions

   https://doi.org/10.1145/3704839  

   Narmour, Louis; Yuki, Tomofumi; Rajopadhye, Sanjay (January 2025, Proceedings of the ACM on Programming Languages)

   Reductions combine collections of input values with an associative and often commutative operator to produce collections of results. When the same input value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduction simplification. Simplification often produces a program with lower asymptotic complexity. Typical compiler optimizations yield, at best, a constant fold speedup, but a complexity improvement from, say, cubic to quadratic complexity yields unbounded speedup for sufficiently large problems. It is well known that reductions in polyhedral programs may be simplified automatically, but previous methods cannot exploit all available reuse. This paper resolves this long-standing open problem, thereby attaining minimal asymptotic complexity in the simplified program. We propose extensions to prior work on simplification to support any independent commutative reduction. At the heart of our approach is piece-wise simplification, the notion that we can split an arbitrary reduction into pieces and then independently simplify each piece. However, the difficulty of using such piece-wise transformations is that they typically involve an infinite number of choices. We give constructive proofs to deal with this and select a finite number of pieces for simplification. 

   more » « less
5. Robustly Guarding Polygons

   https://doi.org/10.4230/LIPIcs.SoCG.2024.47  

   Das, Rathish; Filtser, Omrit; Katz, Matthew J; Mitchell, Joseph SB (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees. 

   more » « less