Abstract
The 3SUM problem represents a class of problems conjectured to require Ω(n2) time to solve, where n is the size of the input. Given two polygons P and Q in R2, we show that some variants of the decision problem, whether there exists a transformation of P that makes it contained in Q, are 3SUM-hard. We also show that finding the translation that minimizes the Hausdorff distance between two segment sets is 3SUM-hard.
| Original language | English (US) |
|---|---|
| Pages | S862-S863 |
| State | Published - 1999 |
| Externally published | Yes |
| Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |
Other
| Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | Baltimore, MD, USA |
| Period | 1/17/99 → 1/19/99 |
ASJC Scopus subject areas
- Software
- General Mathematics