Incorporating FOV events

In the nondeterministic setting, there is no null FOV event. As mentioned in Observation 2, exit and enter FOV events can be handled by converting them into component events. To convert an enter FOV event of shadow $s_i$ into component events, we simply create an appear component event of a single target and and then merge the newly created shadow into $s_i$ . Similarly, an exit FOV event can be converted into a split component event followed by a disappear component event. The rest of the algorithm stays the same. The problem is, however, if there is a large number of FOV events compared to the number of component events, this approach will slow down later steps of the algorithm since it will create two component events per FOV event. Fortunately, there is no reason to handle each FOV event individually; since each FOV event is associated with some shadow, we can group them based on this association. The only caveat is that we cannot just group all FOV events for one shadow into a single batch FOV event as this can introduce information loss. For example, if $e_x, e_x, e_e, e_e$ happens to shadow $s_i$ , this is not equivalent to nothing has happened: we know that $s_i$ must have at least two targets in it originally (a ``surplus''). On the other hand, the just mentioned surplus and net target flow are the only two pieces of information that FOV events of a shadow give us; hence up to two batch FOV events can summarize all information contained in all FOV events for a given shadow. Let $\langle e_j \rangle$ be the sequence of FOV events for a shadow $s_i$ in which $e_j$ is either $e_e$ or $e_x$ , we build a counter to track the surplus of $s_i$ as $d_{\min} = \min\{d_j\}$ , with $d_j$ defined as

$$d_j = \left\{\begin{array}{ll} d_{j-1} + 1 & \textrm{ if } e_j = ... ...} -1 & \textrm{ if } e_j = e_x \\ 0 & \textrm{ if } j = 0. \end{array}\right.$$

Let $d_{\textrm{tot}}$ be $d_j$ for the last $j$ , the net target flow from FOV events. We have four cases. If $d_{\min} = d_{\textrm{tot}} = 0$ , we do nothing. If $d_{\min} \ge 0$ and $d_{\textrm{tot}} > 0$ , we only need to create one batch enter FOV event for $s_i$ with $d_{\textrm{tot}}$ number of targets. If $d_{\min} < 0$ and $d_{\textrm{tot}} = d_{\min}$ , we only need to create one batch exit FOV event with $\vert d_{\min}\vert$ number of targets. In the last case, we need to create one batch exit FOV event with $\vert d_{\min}\vert$ number of targets and then a enter FOV event with $d_{\textrm{tot}} - d_{\min}$ number of targets. We can then apply the naive approach from the beginning of this subsection to convert these batch FOV events into component events. With this construction, we never need to handle more than $5n$ events in which $n$ is the maximum number of shadows.