Geometric Base

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