Reduction from 3SUM' to Static Dihedral Rotation Queries

FROM: 3SUM' TO: Static Dihedral Rotation Queries

Implications

if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$

Year

2003

Reference

Michael Soss, Jeff Erickson, Mark Overmars, Preprocessing chains for fast dihedral rotations is hard or even impossible, Computational Geometry, Volume 26, Issue 3, 2003, Pages 235-246

https://doi.org/10.1016/S0925-7721(02)00156-6