We consider problems related to finding short cycles, small cliques, small independent sets,
and small subgraphs in geometric intersection graphs. We obtain a plethora of new results …

Let $ P $ be a set of $ m $ points in ${\mathbb R}^ 2$, let $\Sigma $ be a set of $ n $ semi-
algebraic sets of constant complexity in ${\mathbb R}^ 2$, let $(S,+) $ be a semigroup, and …

We consider several intersection searching problems that involve lines in \mathbbR^3 and
present improved algorithms for solving them. The problems include (i) ray shooting amid …

Polynomial partitioning techniques have recently led to improved geometric data structures
for a variety of fundamental problems related to semialgebraic range searching and …

Recently, Ezra and Sharir [ES22a] showed an $ O (n^{3/2+\sigma}) $ space and $ O
(n^{1/2+\sigma}) $ query time data structure for ray shooting among triangles in $\mathbb …

Let S be a set of n geometric objects of constant complexity (eg, points, line segments, disks,
ellipses) in R 2, and let ϱ: S× S→ R≥ 0 be a distance function on S. For a parameter r≥ 0 …

Vertical decomposition is a widely used general technique for decomposing the cells of
arrangements of semi-algebraic sets in ℝd into constant-complexity subcells. In this paper …

In the classical linear degeneracy testing problem, we are given n real numbers and ak-
variate linear polynomial F, for some constant k, and have to determine whether there exist k …

We develop data structures for intersection queries in four dimensions that involve
segments, triangles and tetrahedra. Specifically, we study three main problems:(i) …

It is unlikely that the discrete Fr\'echet distance between two curves of length $ n $ can be
computed in strictly subquadratic time. We thus consider the setting where one of the curves …