Geometric Base (Geometric Base)

From Algorithm Wiki
Jump to navigation Jump to search

Description

Given a set of $n$ points with integer coordinates on three horizontal lines $y = 0, y = 1$, and $y = 2$, determine whether there exists a non-horizontal line containing three of the points

Parameters

$n$: number of points

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem Implication Year Citation Reduction
3SUM' if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link
Separator1 if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link
Separator2 if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link
Strips Cover Box if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link
Visibility Between Segments if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link
Visibility From Infinity if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link
Planar Motion Planning if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link

Reductions FROM Problem

Problem Implication Year Citation Reduction
3SUM' if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$
1995 https://doi.org/10.1016/0925-7721(95)00022-2 link