## Abstract

We present subquadratic algorithms in the algebraic decision-tree model for several 3SUM-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ∈C, the number of intersection points between the segments of A and those of B that lie in Δ. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε>0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal et al. (2021) [3]. A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a “handicap” that turns out to be beneficial for speeding up our algorithm.

Original language | English (US) |
---|---|

Article number | 101945 |

Journal | Computational Geometry: Theory and Applications |

Volume | 109 |

DOIs | |

State | Published - Feb 2023 |

## Keywords

- 3SUM-hard problems
- Algebraic decision-tree model
- Order type
- Point location
- Polynomial partitions

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics