We define a close variant of
line range searching over the reals and prove that its arithmetic
complexity is
(
n log
n)
if field operations are allowed and
(
n
3/2) if only
additions are.
This provides the first nontrivial separation
between the monotone and nonmonotone complexity
of a range searching problem.
The result puts into question the
widely held belief that range searching for nonisothetic shapes
typically requires
(
n
1+c
)
arithmetic operations, for some constant
c > 0.