On Fair Epsilon Net and Geometric Hitting Set Conference: ; ;
Mohsen Dehghankar, Stavros Sintos, Abolfazl Asudeh · 2025
Read On Fair Epsilon Net and Geometric Hitting Set Conference: ; ; by Mohsen Dehghankar, Stavros Sintos, Abolfazl Asudeh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08758.txt.
Description
Mohsen Dehghankar, Stavros Sintos, and Abolfazl Asudeh add fairness constraints to classic geometry tools for summarizing data, in a 2025 paper. Epsilon-nets compress point sets while preserving answers to range queries, and hitting sets cover shapes with few points. Neither had been examined for fairness across demographic groups.
The authors define two fairness notions: keeping group shares as in the input, or hitting arbitrary target ratios. They give a fast sampling algorithm whose fair nets grow only slightly with the number of groups, and a slower discrepancy-based one that outputs smaller nets. Fair hitting set reduces to fair nets, yielding a solid approximation. Under some input distributions, they also prove fair samples cannot exist at all, a useful warning. Experiments confirmed zero unfairness at modest size cost. The work opens computational geometry to fairness-aware data systems.
Catalog record
| CREATOR | Mohsen Dehghankar, Stavros Sintos, Abolfazl Asudeh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08758