Thomas Schibler

Mark Wronkiewicz, Jake Lee, Lukas Mandrake et al.

The quest to find extraterrestrial life is a critical scientific endeavor with civilization-level implications. Icy moons in our solar system are promising targets for exploration because their liquid oceans make them potential habitats for microscopic life. However, the lack of a precise definition of life poses a fundamental challenge to formulating detection strategies. To increase the chances of unambiguous detection, a suite of complementary instruments must sample multiple independent biosignatures (e.g., composition, motility/behavior, and visible structure). Such an instrument suite could generate 10,000x more raw data than is possible to transmit from distant ocean worlds like Enceladus or Europa. To address this bandwidth limitation, Onboard Science Instrument Autonomy (OSIA) is an emerging discipline of flight systems capable of evaluating, summarizing, and prioritizing observational instrument data to maximize science return. We describe two OSIA implementations developed as part of the Ocean Worlds Life Surveyor (OWLS) prototype instrument suite at the Jet Propulsion Laboratory. The first identifies life-like motion in digital holographic microscopy videos, and the second identifies cellular structure and composition via innate and dye-induced fluorescence. Flight-like requirements and computational constraints were used to lower barriers to infusion, similar to those available on the Mars helicopter, "Ingenuity." We evaluated the OSIA's performance using simulated and laboratory data and conducted a live field test at the hypersaline Mono Lake planetary analog site. Our study demonstrates the potential of OSIA for enabling biosignature detection and provides insights and lessons learned for future mission concepts aimed at exploring the outer solar system.

Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov et al.

In the Rectangle Stabbing problem, input is a set ${\cal R}$ of axis-parallel rectangles and a set ${\cal L}$ of axis parallel lines in the plane. The task is to find a minimum size set ${\cal L}^* \subseteq {\cal L}$ such that for every rectangle $R \in {\cal R}$ there is a line $\ell \in {\cal L}^*$ such that $\ell$ intersects $R$. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time $2$-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopolous et al. [EuroCG 2009] independently showed that, assuming FPT $\neq$ W[1], there is no algorithm with running time $f(k)(|{\cal L}||{\cal R}|)^{O(1)}$ that determines whether there exists an optimal solution with at most $k$ lines. We give the first parameterized approximation algorithm for the problem with a ratio better than $2$. In particular we give an algorithm that given ${\cal R}$, ${\cal L}$, and an integer $k$ runs in time $k^{O(k)}(|{\cal L}||{\cal R}|)^{O(1)}$ and either correctly concludes that there does not exist a solution with at most $k$ lines, or produces a solution with at most $\frac{7k}{4}$ lines. We complement our algorithm by showing that unless FPT $=$ W[1], the Rectangle Stabbing problem does not admit a $(\frac{5}{4}-ε)$-approximation algorithm running in $f(k)(|{\cal L}||{\cal R}|)^{O(1)}$ time for any function $f$ and $ε> 0$.