9 Search Results for "Das, Rathish"

Document
DOI: 10.4230/LIPIcs.ESA.2025.82
Buffered Partially-Persistent External-Memory Search Trees

Authors: Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present an optimal partially-persistent external-memory search tree with amortized I/O bounds matching those achieved by the non-persistent B^{ε}-tree by Brodal and Fagerberg [SODA 2003]. In a partially-persistent data structure, each update creates a new version. All past versions can be queried, but only the current version can be updated. Operations should be efficient with respect to the size N_v of the accessed version v. For any parameter 0 < ε < 1, our data structure supports insertions and deletions in amortized 𝒪(1/(ε B^{1 - ε}) log_B N_v) I/Os, where B is the external-memory block size. It also supports successor and range reporting queries in amortized 𝒪(1/ε log_B N_v + K/B) I/Os, where K is the number of keys reported. The space usage of the data structure is linear in the total number of updates. We make the standard and minimal assumption that the internal memory has size M ≥ 2B. The previous state-of-the-art external-memory partially-persistent search tree by Arge, Danner and Teh [JEA 2003] supports all operations in worst-case 𝒪(log_B N_v + K/B) I/Os, matching the bounds achieved by the classical B-tree by Bayer and McCreight [Acta Informatica 1972]. Our data structure successfully combines buffering updates with partial persistence. The I/O bounds can also be achieved in the worst-case sense, by slightly modifying our data structure and under the requirement that the memory size M = Ω(B^{1-ε} log₂(max_v N_v)). For updates, where the I/O bound is o(1), we assume that the I/Os are performed evenly spread out among the updates (by performing buffer-overflows incrementally). The worst-case result slightly improves the memory requirement over the previous ephemeral external-memory dictionary by Das, Iacono, and Nekrich (ISAAC 2022), who achieved matching worst-case I/O bounds but required M = Ω(B log_B N), where N is the size of the current dictionary.
Cite as

Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning. Buffered Partially-Persistent External-Memory Search Trees. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 82:1-82:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2025.82,
  author =	{Brodal, Gerth St{\o}lting and Rysgaard, Casper Moldrup and Svenning, Rolf},
  title =	{{Buffered Partially-Persistent External-Memory Search Trees}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{82:1--82:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.82},
  URN =		{urn:nbn:de:0030-drops-245507},
  doi =		{10.4230/LIPIcs.ESA.2025.82},
  annote =	{Keywords: B-tree, buffered updates, partial persistence, external memory}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.39
Sweeping a Domain with Line-Of-Sight Between Covisible Agents

Authors: Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider sweeping a polygonal domain using variable-length segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NP-hard even in simple polygons and even for a single segment (two agents), and give constant-factor approximation algorithms, both for simple polygons and polygons with holes. Our approximations are obtained by introducing a new type of "window partition" of the polygon, which may find other applications. For domains with holes, our results are based on a non-trivial topological argument proving a surprising fact: a connected subset of the domain, whose points are swept but not directly touched by the agents, may contain at most one hole.
Cite as

Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk. Sweeping a Domain with Line-Of-Sight Between Covisible Agents. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.WADS.2025.39,
  author =	{Huynh, Kien C. and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{Sweeping a Domain with Line-Of-Sight Between Covisible Agents}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{39:1--39:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.39},
  URN =		{urn:nbn:de:0030-drops-242706},
  doi =		{10.4230/LIPIcs.WADS.2025.39},
  annote =	{Keywords: Polygon sweeping, collaborating agents, motion coordination, makespan optimization}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.49
On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms

Authors: Lorenzo De Stefani and Vedant Gupta

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms, including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees. Assuming no recomputation of intermediate values, we establish an Ω(n³/(√M B)) I/O lower bound, where n denotes the size of the input and M denotes the size of the available fast memory (cache). When recomputation is allowed, we show that the same bound holds for M < cn, where c is a positive constant. In the case where M ≥ 2n, we show an Ω(n/B) I/O lower bound. We also discuss algorithms for which the number of executed I/O operations matches asymptotically each of the presented lower bounds, which are thus asymptotically tight. Additionally, we refine our general method to obtain a lower bound for the I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the grammar impacts the I/O complexity. An upper bound with asymptotically matching performance in many cases is also provided.
Cite as

Lorenzo De Stefani and Vedant Gupta. On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{destefani_et_al:LIPIcs.WADS.2025.49,
  author =	{De Stefani, Lorenzo and Gupta, Vedant},
  title =	{{On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.49},
  URN =		{urn:nbn:de:0030-drops-242800},
  doi =		{10.4230/LIPIcs.WADS.2025.49},
  annote =	{Keywords: I/O complexity, Dynamic Programming Algorithms, Lower Bounds, Recomputation, Cocke-Younger-Kasami}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.47
Robustly Guarding Polygons

Authors: Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
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.
Cite as

Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell. Robustly Guarding Polygons. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.SoCG.2024.47,
  author =	{Das, Rathish and Filtser, Omrit and Katz, Matthew J. and Mitchell, Joseph S.B.},
  title =	{{Robustly Guarding Polygons}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.47},
  URN =		{urn:nbn:de:0030-drops-199928},
  doi =		{10.4230/LIPIcs.SoCG.2024.47},
  annote =	{Keywords: geometric optimization, approximation algorithms, guarding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.21
External-Memory Dictionaries with Worst-Case Update Cost

Authors: Rathish Das, John Iacono, and Yakov Nekrich

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
The B^ε-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient external-memory-model data structure that supports updates orders of magnitude faster than B-tree with a query performance comparable to the B-tree: for any positive constant ε < 1 insertions and deletions take O(1/B^(1-ε) log_B N) time (rather than O(log_BN) time for the classic B-tree), queries take O(log_B N) time and range queries returning k items take O(log_B N + k/B) time. Although the B^ε-tree has an optimal update/query tradeoff, the runtimes are amortized. Another structure, the write-optimized skip list, introduced by Bender et al. [PODS 2017], has the same performance as the B^ε-tree but with runtimes that are randomized rather than amortized. In this paper, we present a variant of the B^ε-tree with deterministic worst-case running times that are identical to the original’s amortized running times.
Cite as

Rathish Das, John Iacono, and Yakov Nekrich. External-Memory Dictionaries with Worst-Case Update Cost. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2022.21,
  author =	{Das, Rathish and Iacono, John and Nekrich, Yakov},
  title =	{{External-Memory Dictionaries with Worst-Case Update Cost}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.21},
  URN =		{urn:nbn:de:0030-drops-173060},
  doi =		{10.4230/LIPIcs.ISAAC.2022.21},
  annote =	{Keywords: Data Structures, External Memory, Buffer Tree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.59
Shortest Beer Path Queries in Interval Graphs

Authors: Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Anurag Murty Naredla, and Kaiyu Wu

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path. We show that we can represent unweighted interval graphs using 2n log n + O(n) + O(|B|log n) bits where |B| is the number of beer vertices. This data structure answers beer distance queries in O(log^ε n) time for any constant ε > 0 and shortest beer path queries in O(log^ε n + d) time, where d is the beer distance between the two nodes. We also show that proper interval graphs may be represented using 3n + o(n) bits to support beer distance queries in O(f(n)log n) time for any f(n) ∈ ω(1) and shortest beer path queries in O(d) time. All of these results also have time-space trade-offs. Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely log(4+2√3)n - o(n) (or about 2.9 n) bits.
Cite as

Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Anurag Murty Naredla, and Kaiyu Wu. Shortest Beer Path Queries in Interval Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2022.59,
  author =	{Das, Rathish and He, Meng and Kondratovsky, Eitan and Munro, J. Ian and Naredla, Anurag Murty and Wu, Kaiyu},
  title =	{{Shortest Beer Path Queries in Interval Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.59},
  URN =		{urn:nbn:de:0030-drops-173442},
  doi =		{10.4230/LIPIcs.ISAAC.2022.59},
  annote =	{Keywords: Beer Path, Interval Graph}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.16
When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting

Authors: Arghya Bhattacharya, Abiyaz Chowdhury, Helen Xu, Rathish Das, Rezaul A. Chowdhury, Rob Johnson, Rishab Nithyanand, and Michael A. Bender

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Cache-adaptive algorithms are a class of algorithms that achieve optimal utilization of dynamically changing memory. These memory fluctuations are the norm in today’s multi-threaded shared-memory machines and time-sharing caches. Bender et al. [Bender et al., 2014] proved that many cache-oblivious algorithms are optimally cache-adaptive, but that some cache-oblivious algorithms can be relatively far from optimally cache-adaptive on worst-case memory fluctuations. This worst-case gap between cache obliviousness and cache adaptivity depends on a highly-structured, adversarial memory profile. Existing cache-adaptive analysis does not predict the relative performance of cache-oblivious and cache-adaptive algorithms on non-adversarial profiles. Does the worst-case gap appear in practice, or is it an artifact of an unrealistically powerful adversary? This paper sheds light on the question of whether cache-oblivious algorithms can effectively adapt to realistically fluctuating memory sizes; the paper focuses on matrix multiplication and sorting. The two matrix-multiplication algorithms in this paper are canonical examples of "(a, b, c)-regular" cache-oblivious algorithms, which underlie much of the existing theory on cache-adaptivity. Both algorithms have the same asymptotic I/O performance when the memory size remains fixed, but one is optimally cache-adaptive, and the other is not. In our experiments, we generate both adversarial and non-adversarial memory workloads. The performance gap between the algorithms for matrix multiplication grows with problem size (up to 3.8×) on the adversarial profiles, but the gap does not grow with problem size (stays at 2×) on non-adversarial profiles. The sorting algorithms in this paper are not "(a, b, c)-regular," but they have been well-studied in the classical external-memory model when the memory size does not fluctuate. The relative performance of a non-oblivious (cache-aware) sorting algorithm degrades with the problem size: it incurs up to 6 × the number of disk I/Os compared to an oblivious adaptive algorithm on both adversarial and non-adversarial profiles. To summarize, in all our experiments, the cache-oblivious matrix-multiplication and sorting algorithms that we tested empirically adapt well to memory fluctuations. We conjecture that cache-obliviousness will empirically help achieve adaptivity for other problems with similar structures.
Cite as

Arghya Bhattacharya, Abiyaz Chowdhury, Helen Xu, Rathish Das, Rezaul A. Chowdhury, Rob Johnson, Rishab Nithyanand, and Michael A. Bender. When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2022.16,
  author =	{Bhattacharya, Arghya and Chowdhury, Abiyaz and Xu, Helen and Das, Rathish and Chowdhury, Rezaul A. and Johnson, Rob and Nithyanand, Rishab and Bender, Michael A.},
  title =	{{When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.16},
  URN =		{urn:nbn:de:0030-drops-169543},
  doi =		{10.4230/LIPIcs.ESA.2022.16},
  annote =	{Keywords: Cache-adaptive algorithms, cache-oblivious algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.61
Dynamic Boolean Formula Evaluation

Authors: Rathish Das, Andrea Lincoln, Jayson Lynch, and J. Ian Munro

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present a linear space data structure for Dynamic Evaluation of k-CNF Boolean Formulas which achieves O(m^{1-1/k}) query and variable update time where m is the number of clauses in the formula and clauses are of size at most a constant k. Our algorithm is additionally able to count the total number of satisfied clauses. We then show how this data structure can be parallelized in the PRAM model to achieve O(log m) span (i.e. parallel time) and still O(m^{1-1/k}) work. This parallel algorithm works in the stronger Binary Fork model. We then give a series of lower bounds on the problem including an average-case result showing the lower bounds hold even when the updates to the variables are chosen at random. Specifically, a reduction from k-Clique shows that dynamically counting the number of satisfied clauses takes time at least n^{(2ω-3)/6 √{2k} -1 -o(√k)}, where 2 ≤ ω < 2.38 is the matrix multiplication constant. We show the Combinatorial k-Clique Hypothesis implies a lower bound of m^{(1-k^{-1/2})(1-o(1))} which suggests our algorithm is close to optimal without involving Matrix Multiplication or new techniques. We next give an average-case reduction to k-clique showing the prior lower bounds hold even when the updates are chosen at random. We use our conditional lower bound to show any Binary Fork algorithm solving these problems requires at least Ω(log m) span, which is tight against our algorithm in this model. Finally, we give an unconditional linear space lower bound for Dynamic k-CNF Boolean Formula Evaluation.
Cite as

Rathish Das, Andrea Lincoln, Jayson Lynch, and J. Ian Munro. Dynamic Boolean Formula Evaluation. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 61:1-61:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2021.61,
  author =	{Das, Rathish and Lincoln, Andrea and Lynch, Jayson and Munro, J. Ian},
  title =	{{Dynamic Boolean Formula Evaluation}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{61:1--61:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.61},
  URN =		{urn:nbn:de:0030-drops-154945},
  doi =		{10.4230/LIPIcs.ISAAC.2021.61},
  annote =	{Keywords: Data Structures, SAT, Dynamic Algorithms, Boolean Formulas, Fine-grained Complexity, Parallel Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.7
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

Authors: Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
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.
Cite as

Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth. Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.ESA.2020.7,
  author =	{Arkin, Esther M. and Das, Rathish and Gao, Jie and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin and T\'{o}th, Csaba D.},
  title =	{{Cutting Polygons into Small Pieces with Chords: Laser-Based Localization}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.7},
  URN =		{urn:nbn:de:0030-drops-128736},
  doi =		{10.4230/LIPIcs.ESA.2020.7},
  annote =	{Keywords: Polygon partition, Arrangements, Visibility, Localization}
}
  • Refine by Type
  • 9 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2024
  • 3 2022
  • 1 2021
  • 1 2020

  • Refine by Author
  • 6 Das, Rathish
  • 2 Mitchell, Joseph S. B.
  • 2 Munro, J. Ian
  • 2 Polishchuk, Valentin
  • 1 Arkin, Esther M.
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Data structures design and analysis
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Paths and connectivity problems
  • Show More...

  • Refine by Keyword
  • 2 Data Structures
  • 1 Arrangements
  • 1 B-tree
  • 1 Beer Path
  • 1 Boolean Formulas
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact