Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.07617 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912187372535808 |
|---|---|
| author | Csikós, Mónika Louvet, Alexandre Mustafa, Nabil |
| author_facet | Csikós, Mónika Louvet, Alexandre Mustafa, Nabil |
| contents | Simplicial partitions are a fundamental structure in computational geometry, as they form the basis of optimal data structures for range searching and several related problems. Current algorithms are built on very specific spatial partitioning tools tailored for certain geometric cases. This severely limits their applicability to general set systems. In this work, we propose a simple greedy heuristic for constructing simplicial partitions of any set system. We present a thorough empirical evaluation of its behavior on a variety of geometric and non-geometric set systems, showing that it performs well on most instances. Implementation of these algorithms is available on Github. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07617 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Greedy Algorithm for Low-Crossing Partitions for General Set Systems Csikós, Mónika Louvet, Alexandre Mustafa, Nabil Computational Geometry Simplicial partitions are a fundamental structure in computational geometry, as they form the basis of optimal data structures for range searching and several related problems. Current algorithms are built on very specific spatial partitioning tools tailored for certain geometric cases. This severely limits their applicability to general set systems. In this work, we propose a simple greedy heuristic for constructing simplicial partitions of any set system. We present a thorough empirical evaluation of its behavior on a variety of geometric and non-geometric set systems, showing that it performs well on most instances. Implementation of these algorithms is available on Github. |
| title | A Greedy Algorithm for Low-Crossing Partitions for General Set Systems |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2501.07617 |