New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:30, 15 February 2023 Disjunctive coBüchi Objectives (hist | edit) [1,984 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Disjunctive coBüchi Objectives (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is coBüchi: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that visits the set $T$ a finite amount of times. Furthermore, in the disjunctive problem, you a...")
- 10:30, 15 February 2023 Disjunctive Queries of Safety in Graphs (hist | edit) [2,360 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Disjunctive Queries of Safety in Graphs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). Furthe...")
- 10:30, 15 February 2023 Safety in Graphs (hist | edit) [1,054 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Safety in Graphs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). == Related Problems == Subp...")
- 10:30, 15 February 2023 Conjunctive Safety Queries in MDPs (hist | edit) [1,311 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Conjunctive Safety Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in...")
- 10:30, 15 February 2023 Disjunctive Safety Queries in MDPs (hist | edit) [1,309 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Disjunctive Safety Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in...")
- 10:30, 15 February 2023 Safety in MDPs (hist | edit) [1,084 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Safety in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). == Related Pr...")
- 10:30, 15 February 2023 Conjunctive Reachability Queries in MDPs (hist | edit) [1,338 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Conjunctive Reachability Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach...")
- 10:30, 15 February 2023 Disjunctive Reachability Queries in MDPs (hist | edit) [2,262 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Disjunctive Reachability Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach...")
- 10:30, 15 February 2023 Reachability in MDPs (hist | edit) [1,082 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Reachability in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach some vertex in $T$)....")
- 10:30, 15 February 2023 Maximum Inner Product Search (hist | edit) [2,800 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Inner Product Search (Maximum Inner Product Search)}} == Description == Given a new query $q$, MIPS targets at retrieving the datum having the largest inner product with $q$ from the database $A$. Formally, the MIPS problem is formulated as below: $p = \arg \max \limits_{a \in A} a \top q$ == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem...")
- 10:29, 15 February 2023 RNA Folding (hist | edit) [1,330 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:RNA Folding (RNA Folding)}} == Description == In RNA Folding we are given a string over some alphabet (e.g. $\{A, C, G, T\}$) with a fixed pairing between its symbols (e.g. $A − T$ match and $C − G$ match), and the goal is to compute the maximum number of non-crossing arcs between matching letters that one can draw above the string (which corresponds to the minimum energy folding in two dimensions). == Parameters == <pre>n: length of the given str...")
- 10:29, 15 February 2023 Ap-reach (hist | edit) [1,069 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:ap-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$, determine for each pair $s \neq t \in V$ whether $t$ is reachable from $s$. == Related Problems == Generalizations: st-Reach Related: #SSR, sensitive incremental #SSR, ST-Reach, constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach == Parameters == <pre>n: number of vertices m: num...")
- 10:29, 15 February 2023 2-sensitive incremental st-reach (hist | edit) [1,152 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-sensitive incremental st-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and vertices $s, t \in V$, incrementally determine wheteher $t$ is reachable from $s$, with sensitivity 2, i.e. when 2 edges are added. == Related Problems == Generalizations: st-Reach Related: #SSR, sensitive incremental #SSR, ST-Reach, constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, ap-re...")
- 10:29, 15 February 2023 1-sensitive incremental ss-reach (hist | edit) [1,325 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive incremental ss-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and a source node $s \in G$, an incremental single-source reachability algorithm maintains the set of nodes reachable from $s$ (i.e., all nodes $v$ for which there is a path from $s$ to $v$ in the current version of $G$) during a sequence of edge insertions, with sensitivity 1, i.e. when 1 edge is inserted. == Related Problems == Generalizations...")
- 10:29, 15 February 2023 Constant sensitivity incremental ST-Reach (hist | edit) [688 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:constant sensitivity incremental ST-Reach (Vertex Reachability)}} == Description == Given a graph $G=(V,E)$, incrementally determine whether each node $s\in S\subseteq V$ can reach a node $t\in T \subseteq V$, with a constant sensitivity of $K(\epsilon, t)$, i.e. when $K(\epsilon, t)$ edges are added. == Related Problems == Generalizations: ST-Reach Related: #SSR, sensitive incremental #SSR, st-Reach, 1-sensitive incremental ss-reac...")
- 10:29, 15 February 2023 St-Reach (hist | edit) [663 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:st-Reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and vertices $s, t \in V$, determine wheteher $t$ is reachable from $s$. == Related Problems == Subproblem: constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach, ap-reach Related: #SSR, sensitive incremental #SSR, ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive increm...")
- 10:29, 15 February 2023 ST-Reach (hist | edit) [669 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:ST-Reach (Vertex Reachability)}} == Description == Given a graph $G=(V,E)$, determine whether each node $s\in S\subseteq V$ can reach a node $t\in T \subseteq V$. == Related Problems == Subproblem: constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach, ap-reach Related: #SSR, sensitive incremental #SSR, st-Reach, 1-sensitive incremental ss-reach, 2-sensitive...")
- 10:29, 15 February 2023 Sensitive incremental (hist | edit) [1,752 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:sensitive incremental #SSR (Vertex Reachability)}} == Description == A data structure with sensitivity $d$ for a problem $P$ has the following properties: It obtains an instance $p$ of $P$ and is allowed polynomial preprocessing time on $p$. After the preprocessing, the data structure must provide the following operations: (Batch) Update: Up to $d$ changes are performed to the initial problem instance $p$, e.g., $d$ edges are added to or removed from $p...")
- 10:29, 15 February 2023 Online Vector-Matrix-Vector Multiplication (hist | edit) [1,288 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Online Vector-Matrix-Vector Multiplication (Matrix-Vector Multiplication)}} == Description == Let $M$ be a binary $n \times n$ matrix than can be preprocessed. After preprocessing $n$ vector pairs $(u^1, v^1), \ldots, (u^n, v^n)$, arrive one at a time and the task is to compute $(u^i)^T M v^i$ before being presented with the $i+1$th vector pair for every $i$. == Related Problems == Related: Online Matrix-Vector Multiplication == Parameters == <...")
- 10:29, 15 February 2023 Online Matrix-Vector Multiplication (hist | edit) [690 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Online Matrix-Vector Multiplication (Matrix-Vector Multiplication)}} == Description == We are given an $n \times n$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1, \ldots , v_n$, one by one. After seeing each vector $v_i$, we have to output the product $Mv_i$ before we can see the next vector. == Related Problems == Related: Online Vector-Matrix-Vector Multiplication == Parameters == <pre>n: dimension of square matr...")
- 10:29, 15 February 2023 Shortest k-Cycle (hist | edit) [1,042 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Shortest k-Cycle (Graph Cycles)}} == Description == Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle of length $k$. == Related Problems == Generalizations: Shortest Cycle == Parameters == <pre>n: number of vertices m: number of edges k: length of cycle</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" sty...")
- 10:29, 15 February 2023 Shortest Cycle (hist | edit) [901 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Shortest Cycle (Graph Cycles)}} == Description == Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle. == Related Problems == Subproblem: Shortest k-Cycle == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 10:29, 15 February 2023 Price Query (hist | edit) [1,235 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Price Query (Price Query)}} == Description == For a graph with edge weight function $c : E \rightarrow Z$, a price query is an assignment of node weights $p : V \rightarrow Z$. Such a query has a yes answer if and only if there is a $(u,v) \in E$ such that $p(u) + p(v) > c(u,v)$. (Intuitively, the $p(v)$ are “prices” on the nodes, the $c(u,v)$ are costs of producing $u$ and $v$, and a price query asks if there is an edge we are willing to “sell”...")
- 10:29, 15 February 2023 Independent Set Queries (hist | edit) [1,358 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Independent Set Queries (Independent Set Queries)}} == Description == For a graph $G=(V,E)$ and a given subset of vertices $S\subseteq G$, answer the query of the form "is $S$ an independent set?" == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width=...")
- 10:29, 15 February 2023 All Pairs Minimum Witness (hist | edit) [962 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All Pairs Minimum Witness (Minimum Witness)}} == Description == Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(...")
- 10:29, 15 February 2023 Minimum Witness Finding (hist | edit) [1,429 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum Witness Finding (Minimum Witness)}} == Description == Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(i,...")
- 10:29, 15 February 2023 Multiple Local Alignment (hist | edit) [1,031 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Multiple Local Alignment (Local Alignment)}} == Description == Given $k$ input strings and a scoring function on pairs of letters, one is asked to find the substrings of the $k$ input strings that are most similar under the scoring function. == Related Problems == Generalizations: Local Alignment == Parameters == <pre>k: number of input strings n: length of input strings?</pre> == Table of Algorithms == Currently no algorithms in our databas...")
- 10:29, 15 February 2023 Local Alignment (hist | edit) [1,348 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Local Alignment (Local Alignment)}} == Description == Given two input strings and a scoring function on pairs of letters, one is asked to find the substrings of the two input strings that are most similar under the scoring function. == Related Problems == Subproblem: Multiple Local Alignment == Parameters == <pre>n: length of input strings?</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Red...")
- 10:29, 15 February 2023 Geometric Base (hist | edit) [3,034 bytes] Admin (talk | contribs) (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...")
- 10:29, 15 February 2023 3D Motion Planning (hist | edit) [1,079 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3D Motion Planning (Motion Planning Problems)}} == Description == Given a set of horizontal (that is, parallel to the xy-plane) non-intersecting, non-touching triangle obstacles in 3-space, and a vertical line segment as a robot, determine whether the robot can be moved, using translations only, from a source to a goal position without colliding with the obstacles. == Related Problems == Related: Planar Motion Planning == Parameters == <pre>n:...")
- 10:29, 15 February 2023 Planar Motion Planning (hist | edit) [1,158 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Planar Motion Planning (Motion Planning Problems)}} == Description == Given a set of non-intersecting, non-touching, axis-parallel line segment obstacles in the plane and a line segment robot (a rod or ladder), determine whether the rod can be moved (allowing both translation and rotation) from a given source to a given goal configuration without colliding with the obstacles. == Related Problems == Related: 3D Motion Planning == Parameters == <...")
- 10:29, 15 February 2023 Visible Triangle (hist | edit) [1,457 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Visible Triangle (Geometric Visibility Problems)}} == Description == Given a set $S$ of opaque horizontal triangles, another horizontal triangle $t$ and a viewpoint $p$, is there a point on $t$ that can be seen from $p$? == Related Problems == Related: Visibility Between Segments, Visibility From Infinity == Parameters == <pre>n: number of opaque horizontal triangles</pre> == Table of Algorithms == Currently no algorithms in our database...")
- 10:29, 15 February 2023 Visibility From Infinity (hist | edit) [1,088 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Visibility From Infinity (Geometric Visibility Problems)}} == Description == Given a set $S$ of axis-parallel line segments in the plane and one particular horizontal segments $s$, determine whether there is a point on $s$ that can be seen from infinity, that is, whether there exists an infinite ray starting at the point on $s$ that does not intersect any segment. == Related Problems == Related: Visibility Between Segments, Visible Triangle =...")
- 10:29, 15 February 2023 Visibility Between Segments (hist | edit) [1,088 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Visibility Between Segments (Geometric Visibility Problems)}} == Description == Given a set $S$ of $n$ horizontal line segments in the plane and two particular horizontal segments $s_1$ and $s_2$, determine whether there are points on $s_1$ and $s_2$ that can see each other, that is, such that the open segment between the points does not intersect any segment in $S$. == Related Problems == Related: Visibility From Infinity, Visible Triangle =...")
- 10:29, 15 February 2023 Weighted Depth (hist | edit) [1,239 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Weighted Depth (Geometric Covering Problems)}} == Description == Given a set of $n$ weighted axis-parallel boxes in $d$-dimensional space $\mathbb{R}^d$, find a point $p \in \mathbb{R}^d$ that maximizes the sum of the weights of the boxes containing $p$. == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle == Parameters == <pre>n: nu...")
- 10:29, 15 February 2023 Max-Weight Rectangle (hist | edit) [1,216 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Max-Weight Rectangle (Geometric Covering Problems)}} == Description == Given $n$ weighted points (positive or negative) in $d \geq 2$ dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Weighted Depth == Parameters == <pre>n: number of points d: dimensio...")
- 10:29, 15 February 2023 Point Covering (hist | edit) [997 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Point Covering (Geometric Covering Problems)}} == Description == Given a set of $n$ halfplanes and a number $k$, determine whether there is a point $p$ that is covered by at least $k$ of the halfplanes. == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of halfplanes</pre> == Table of Algorithms ==...")
- 10:29, 15 February 2023 Triangle Measure (hist | edit) [951 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Triangle Measure (Geometric Covering Problems)}} == Description == Given a set of triangles in the plane, compute the measure of their union. == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of triangles</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem....")
- 10:29, 15 February 2023 Hole in Union (hist | edit) [1,425 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Hole in Union (Geometric Covering Problems)}} == Description == Given a set of triangles in the plane, does their union contain a hole? == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Triangle Measure, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of triangles</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. =...")
- 10:29, 15 February 2023 Triangles Cover Triangle (hist | edit) [2,953 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Triangles Cover Triangle (Geometric Covering Problems)}} == Description == Given a set of triangles in the plane, does their union contain another given triangle? == Related Problems == Related: Strips Cover Box, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of triangles</pre> == Table of Algorithms == Currently no algorithms in our database for the g...")
- 10:29, 15 February 2023 Strips Cover Box (hist | edit) [1,712 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Strips Cover Box (Geometric Covering Problems)}} == Description == Given a set of strips in the plane, does their union contain a given axis-parallel rectangle? == Related Problems == Related: Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of strips</pre> == Table of Algorithms == Currently no algorithms in our database for th...")
- 10:29, 15 February 2023 Separator2 (hist | edit) [831 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Separator2 (Geometric Separator Problems)}} == Description == Given a set $S$ of $n$ closed, non-intersecting (nor touching), axis-parallel line segments, is there a separator? == Related Problems == Related: Separator1 == Parameters == <pre>n: number of line segments</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align...")
- 10:29, 15 February 2023 Separator1 (hist | edit) [1,068 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Separator1 (Geometric Separator Problems)}} == Description == Given a set $S$ of $n$ possible half-infinite, closed horizontal line segments, is there a non-horizontal separator? Separator definition: Given a set $S$ of $n$ objects in the plane, we call a line $l$ a separator of $S$ if $l$ does not intersect any object in $S$ and both halfplanes bounded by $l$ contain a non-empty subset of the objects in $S$. == Related Problems == Related: Separat...")
- 10:28, 15 February 2023 Point on 3 Lines (hist | edit) [1,298 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Point on 3 Lines (Geometric Incidence Problems)}} == Description == Given a set of lines in the plane, is there a point that lies on at least three of them? == Related Problems == Related: 3 Points on Line == Parameters == <pre>n: number of lines</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 10:28, 15 February 2023 3 Points on Line (hist | edit) [1,580 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3 Points on Line (Geometric Incidence Problems)}} == Description == Given a set of points in the plane, is there a line that contains at least three of the points? == Related Problems == Related: Point on 3 Lines == 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-align:center;" width=...")
- 10:28, 15 February 2023 Partial Match (hist | edit) [1,585 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Partial Match (Partial Match)}} == Description == In the Partial Match problem, we are given a "database" of $n$ binary strings, and a list of $n$ "queries" which are strings in $\{0,1,?\}^*$. (Here, "?" represents a wildcard.) We say that a query $q=q_1,...,q_d$ matches a string $x=x_1,...,x_d$ if for all $i=1,...,d$, if $q_i$ in $\{0,1\}$ then $q_i = x_i$. Output: Determine for all $n$ queries, which of them match some string in the database. == Param...")
- 10:28, 15 February 2023 Dynamic Time Warping (hist | edit) [1,191 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dynamic Time Warping (Dynamic Time Warping)}} == Description == Fix a metric space $(M, d)$. A sequence of points in $M$ is called a curve. Consider two curves $x, y$ of length $n, m (n \geq m)$. We may traverse $x$ and $y$ by starting in their first entries, in any time step advancing to the next entry in $x$ or $y$ or both, and ending in their last entries. The cost of such a traversal is the sum over all points in time of the distance between the curr...")
- 10:28, 15 February 2023 Frechet Distance (hist | edit) [981 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Frechet Distance (Frechet Distance)}} == Description == Intuitively, the (continuous) Fréchet distance of two curves $P, Q$ is the minimal length of a leash required to connect a dog to its owner, as they walk along $P$ or $Q$, respectively, without backtracking. == Parameters == <pre>n: length of first curve m: length of second curve</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FRO...")
- 10:28, 15 February 2023 Metricity (hist | edit) [1,534 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Metricity (Metricity)}} == Description == Given an $n\times n$ nonnegative matrix $A$, determine whether $A$ defines a metric on $(n)$, that is, that A is symmetric, has 0s on the diagonal, and its entries satisfy the triangle inequality. == Parameters == <pre>n: dimensionality of matrix</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable sortable" style=...")
- 10:28, 15 February 2023 Triangle Collection* (hist | edit) [2,241 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Triangle Collection* (Graph Triangle Problems)}} == Description == See Definition 3 of reference. == Related Problems == Generalizations: Triangle Detection Related: Negative Triangle Detection, Negative Triangle Search, Negative Triangle Listing, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted Graph == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Curren...")