Geometric Base: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:Geometric Base (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 == <pre>n: number of points</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable sortable" style="text...")
 
No edit summary
 
(One intermediate revision by the same user not shown)
Line 6: Line 6:
== Parameters ==  
== Parameters ==  


<pre>n: number of points</pre>
$n$: number of points


== Table of Algorithms ==  
== Table of Algorithms ==  

Latest revision as of 08:27, 10 April 2023

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