Overview
This problem is NP-hard; more precisely, the associated decision problem (in which we ask whether a target number of tridents $k$ can cover all of the given $x_i$s) is NP-hard. We will refer to this decision problem as the Numerical Trident Cover Problem.
To prove that the Numerical Trident Cover Problem is NP-hard, we introduce the following intermediate problem, which we will call the Grid Triangle Cover Problem:
Input: A finite set $S \subset \mathbb{Z}^+ \times \mathbb{Z}^+$ of integer coordinate pairs and an integer value $k$.
Output: Yes or no, with an output of yes if and only if there exists a set $T \subset \mathbb{Z} \times \mathbb{Z}$ with $|T| \le k$ such that $S \subseteq \bigcup_{(x,y) \in T} \{(x, y), (x, y+1), (x+1, y)\}$
Thinking about this problem graphically, we are given a subset of the integer lattice and asked to cover every point in this subset with $k$ side-length-$(1, 1, \sqrt{2})$ right triangles in a particular orientation (in particular these triangles must have vertices of the form $(x, y)$, $(x, y+1)$, and $(x+1, y)$). We are asked to say yes if and only if this is possible.
To show that Numerical Trident Cover is NP-hard, we provide two reductions: a reduction from Planar 3SAT to Grid Triangle Cover and a reduction from Grid Triangle Cover to Numerical Trident Cover. Together, these compose into a reduction from the NP-hard problem Planar 3SAT to the Numerical Trident Cover problem, implying that Numerical Trident Cover is NP-hard.
Note that since we are using real numbers in the Numerical Trident Cover Problem, the issue of encoding and input size should come up. We avoid this problem by always using numbers of the form $p + q\sqrt{2}$ in our Numerical Trident Cover instances, allowing for an efficient encoding simply by encoding $p + q\sqrt{2}$ as $(p, q)$. In fact, the problem is still hard even if the numbers are further restricted to be integers, though that reduction requires a bit more work, and is therefore omitted here.
Reduction 1: From Grid Triangle Cover to Numerical Trident Cover.
Suppose we are given an instance of the Grid Triangle Cover problem consisting of a set $S \subseteq \mathbb{Z}^+ \times \mathbb{Z}^+$ and a number $k$.
Then we construct an instance of Numerical Trident Cover (consisting of a list of real numbers $x_1, ..., x_N$, a pair $a, b$, and a target number of tridents $k'$) as follows.
Let the elements of $S$ be $s_1 = (p_1, q_1), s_2 = (p_2, q_2), ..., s_{|S|} = (p_{|S|}, q_{|S|})$. For each $i$ from $1$ to $N = |S|$ let $x_i = -p_i + q_i \sqrt{2}$. Let $a = 1$ and $b = \sqrt{2}$. Finally, let $k' = k$. This is the output instance of Numerical Trident Cover.
This reduction is clearly a polynomial time operation, so the only thing left to show is that the reduction is answer preserving.
To do this, consider the "reasonable" places to put the tridents. The only places where we can put a trident so that it hits at least one $x_i$ are locations of the form $x_i$, $x_i + a$, or $x_i - b$. For each of the $x_i$s, these three values are all of the form $-v_a + v_b \sqrt{2}$ for some integers $v_a$ and $v_b$. Thus we can restrict our attention to numbers of the form $-v_a + v_b \sqrt{2}$. Define the bijection $f$ between the set of all $p + q \sqrt{2}$ and the set of all pairs of integers according to the rule $f(-v_a + v_b\sqrt{2}) = (v_a, v_b)$. Note that $f$ maps $x_i$ to $s_i$.
Also note that if a trident is located at $-p + q\sqrt{2}$ then its three prongs are located at $-(p+1) + q\sqrt{2}$, $-p + q\sqrt{2}$, and $-p + (q+1)\sqrt{2}$. In other words, the image of the three prongs under $f$ consists of points $(p,q)$, $(p+1, q)$, and $(p, q+1)$. The image of a trident under $f$ is exactly a triangle of the form we are using to cover the values in $S$. Similarly, every properly oriented triangle maps to a trident under $f^{-1}$. In fact, the triangles and tridents are in exact bijection under $f$.
Since $f$ is bijective, it is clearly the case that some set of tridents covers $\{x_1, ..., x_{|S|}\}$ if and only if the images of those tridents under $f$ cover $S = \{s_1, ..., s_{|S|}\} = \{f(x_1), ..., f(x_{|S|})\}$. Then since the image of a trident under $f$ is a side-length-$(1,1\sqrt{2})$ triangle in the proper orientation, we can conclude that we can cover the $x_i$s with $k$ tridents if and only if we can cover the set $S$ with $k$ side-length-$(1,1\sqrt{2})$ triangles in the proper orientation. We conclude that the reduction is answer preserving.
Reduction 2: From Planar 3SAT to Grid Triangle Cover.
For this reduction, we are given a 3SAT instance in the form of a planar bipartite graph. The vertices in one part correspond to variables, and the vertices of the other part, each of degree 3, correspond to clauses. Each edge is labeled as positive or negative, indicating which way the variable is included into the clause (positively or negatively).
Then we can construct a Grid Triangle Cover instance $(S, k)$. We can construct $S$ out of variable gadgets, clause gadgets, and wire gadgets. After describing these gadgets and their desired behaviors, we will be able to describe how $k$ is computed.
First we describe a wire. A wire consists of a sequence of an odd number of points (in the integer lattice) where the first and last are called terminals such that every consecutive pair can be covered by a triangle without the triangle hitting any other point in the wire. As an example consider the following wire:
xoo x
o o
o ooo o
o o oooo
oo
The point of a wire is that it can be satisfied using a minimum number of covering triangles in two ways. In particular, if $p$ is the number of non-terminal points in the wire ("o"s in the above example) then $\frac{p+1}{2}$ triangles are necessary and those triangles will, in addition to covering the non-terminal points, cover exactly one of the two terminals.
Here we show the two ways to cover the example from above (where two points are labeled the same number if they are covered by the same triangle):
x11 9
2 9
2 556 8
3 4 6778
34
or
112 x
2 9
3 566 9
3 5 7788
44
One concern is that we might wish to connect two terminals with a wire but be unable to do so because any "wire" between those two terminals would have even length. However, that is not the case: we can always choose a route for a wire to make that wire have odd length (and therefore be a valid wire). Replacing any horizontal segment of wire of length 6 with the following length 7 wire segment can fix the parity of the wire length:
oo oo
ooo
Next we introduce a clause gadget. A clause simply connects one of the terminals of three wires in such a way that if one of the wires is satisfied so that the shared terminal is covered, then the triangle covering that shared terminal does not cover any points from the other wires:
o
o
o
ooox
ooo
In order for the shared terminal to be covered, at least one of the three wires must be satisfies in such a way that the triangles satisfying the wire do not cover the wires' non-shared terminal.
Finally, we introduce the variable gadget. The variable gadget is a large wire-like loop (of even length) with terminals optionally occurring to the side every three rows as follows:
oo
o o
o ox
o o
o o
o ox
o o
o o
o ox
o o
o o
o ox
o o
oo
The variable can grow vertically to accommodate the necessary number of terminals The terminals on rows of even parity correspond to positive occurrences of the variable and those on rows of odd parity correspond to negative occurrences. As with wire, the non-terminal points of the variable gadget can be satisfied using the minimum number of triangles (half the number of points in the loop) in exactly two ways. Those two settings cover either all the positive occurrence terminals or all the negative occurrence terminals of the variable gadget.
Putting it all together is pretty obvious: we build the bipartite graph using variable gadgets, clause gadgets (shared terminals) and wires connecting the terminals. The total number of triangles necessary to cover the non-terminal points of the wires and variables is then the target number of triangles.
Clearly we cannot cover the entire grid with fewer than that triangles. Furthermore, we can be assured that the non-terminal points are each covered since the variables and wires will each be satisfied in one of the two ways described. Thus the only task is to satisfy the terminals.
At each variable, either all the positive or all the negative occurrence terminals will be satisfied by the variable gadget. The other terminals at the gadget have to be satisfied by their attached wires. Then the clause terminals can be satisfied if and only if every clause is attached to at least one wire whose other terminal did not already use up the wire (a wire whose other terminal was satisfied by its attached variable gadget). In other words, the terminals are all satisfied if and only if the assignment of variables according to the settings of the variable gadgets satisfies every clause.
As you can see, the produced Grid Triangle Cover instance is a yes instance if and only if the input Planar 3SAT instance is a yes instance. Since this reduction is also polynomial time (all of the gadgets require space polynomial in the size of the input instance), we conclude that we have a valid reduction.
