Search

Let $\mathcal{P}$ be a set of $n=2m+1$ points in the plane in general position. We define the graph $GM_\mathcal{P}$ whose vertex set is the set of all plane matchings on $\mathcal{P}$ with exactly $m$ edges. Two vertices in $GM_\mathcal{P}$ are connected if the two corresponding matchings have $m-1$ edges in common. In this work we show that $GM_\mathcal{P}$ is connected and give an upper bound of $O(n^2)$ on its diameter. Moreover, we present a tight bound of $\Theta(n)$ for the diameter of the flip graph of points in convex position., Comment: Appeared in CCCG2024

While multimodal foundation models can now natively work with data beyond text, they remain underutilized in analyzing the considerable amounts of multi-dimensional time-series data in fields like healthcare, finance, and social sciences, representing a missed opportunity for richer, data-driven insights. This paper proposes a simple but effective method that leverages the existing vision encoders of these models to "see" time-series data via plots, avoiding the need for additional, potentially costly, model training. Our empirical evaluations show that this approach outperforms providing the raw time-series data as text, with the additional benefit that visual time-series representations demonstrate up to a 90% reduction in model API costs. We validate our hypothesis through synthetic data tasks of increasing complexity, progressing from simple functional form identification on clean data, to extracting trends from noisy scatter plots. To demonstrate generalizability from synthetic tasks with clear reasoning steps to more complex, real-world scenarios, we apply our approach to consumer health tasks - specifically fall detection, activity recognition, and readiness assessment - which involve heterogeneous, noisy data and multi-step reasoning. The overall success in plot performance over text performance (up to an 120% performance increase on zero-shot synthetic tasks, and up to 150% performance increase on real-world tasks), across both GPT and Gemini model families, highlights our approach's potential for making the best use of the native capabilities of foundation models., Comment: 57 pages

The Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-known that the Necklace Splitting problem reduces to the discrete Ham Sandwich problem. This reduction was crucial in the proof of PPA-completeness of the Ham Sandwich problem. Recently, Borzechowski, Schnider and Weber [ISAAC'23] introduced a variant of Necklace Splitting that similarly reduces to the $\alpha$-Ham Sandwich problem, which lies in the complexity class UEOPL but is not known to be complete. To make this reduction work, the input necklace is guaranteed to be n-separable. They showed that these necklaces can be fairly split in polynomial time and thus this subproblem cannot be used to prove UEOPL-hardness for $\alpha$-Ham Sandwich. We consider the more general unfair necklace splitting problem on n-separable necklaces, i.e., the problem of splitting these necklaces such that each thief gets a desired fraction of each type of jewels. This more general problem is the natural necklace-splitting-type version of $\alpha$-Ham Sandwich, and its complexity status is one of the main open questions posed by Borzechowski, Schnider and Weber. We show that the unfair splitting problem is also polynomial-time solvable, and can thus also not be used to show UEOPL-hardness for $\alpha$-Ham Sandwich., Comment: 34 pages, 14 figures

We present AuToMATo, a novel clustering algorithm based on persistent homology. While AuToMATo is not parameter-free per se, we provide default choices for its parameters that make it into an out-of-the-box clustering algorithm that performs well across the board. AuToMATo combines the existing ToMATo clustering algorithm with a bootstrapping procedure in order to separate significant peaks of an estimated density function from non-significant ones. We perform a thorough comparison of AuToMATo (with its parameters fixed to their defaults) against many other state-of-the-art clustering algorithms. We find not only that AuToMATo compares favorably against parameter-free clustering algorithms, but in many instances also significantly outperforms even the best selection of parameters for other algorithms. AuToMATo is motivated by applications in topological data analysis, in particular the Mapper algorithm, where it is desirable to work with a clustering algorithm that does not need tuning of its parameters. Indeed, we provide evidence that AuToMATo performs well when used with Mapper. Finally, we provide an open-source implementation of AuToMATo in Python that is fully compatible with the standard scikit-learn architecture.

We show that each set of $n\ge 2$ points in the plane in general position has a straight-line matching with at least $(5n+1)/27$ edges whose segments form a connected set, and such a matching can be computed in $O(n \log n)$ time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has $\lceil \frac{n-1}{3}\rceil$ edges. We also consider a colored version, where each edge of the matching should connect points with different colors., Comment: 20 pages, 14 figures; preliminary version in EuroCG 2024

Imagine you are a dog behind a fence $Q$ and a hiker is passing by at constant speed along the hiking path $P$. In order to fulfil your duties as a watchdog, you desire to bark as long as possible at the human. However, your barks can only be heard in a fixed radius $\rho$ and, as a dog, you have bounded speed $s$. Can you optimize your route along the fence $Q$ in order to maximize the barking time with radius $\rho$, assuming you can run backwards and forward at speed at most $s$? We define the barking distance from a polyline $P$ on $n$ vertices to a polyline $Q$ on $m$ vertices as the time that the hiker stays in your barking radius if you run optimally along $Q$. This asymmetric similarity measure between two curves can be used to detect outliers in $Q$ compared to $P$ that other established measures like the Fr\'echet distance and Dynamic Time Warping fail to capture at times. We consider this measure in three different settings. In the discrete setting, the traversals of $P$ and $Q$ are both discrete. For this case we show that the barking distance from $P$ to $Q$ can be computed in $O(nm\log s)$ time. In the semi-discrete setting, the traversal of $Q$ is continuous while the one of $P$ is again discrete. Here, we show how to compute the barking distance in time $O(nm\log (nm))$. Finally, in the continuous setting in which both traversals are continuous, we show that the problem can be solved in polynomial time. For all the settings we show that, assuming SETH, no truly subquadratic algorithm can exist.

Enclosing depth is a recently introduced depth measure which gives a lower bound to many depth measures studied in the literature. So far, enclosing depth has only been studied from a combinatorial perspective. In this work, we give the first algorithms to compute the enclosing depth of a query point with respect to a data point set in any dimension. In the plane we are able to optimize the algorithm to get a runtime of O(n log n). In constant dimension, our algorithms still run in polynomial time.

We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sink orientation (USO), and a variant of the $\alpha$-Ham Sandwich problem. For all three settings, we show that "two choices are enough", meaning that the general non-binary version of the problem can be reduced in polynomial time to the binary version. This specifically means that generalized P-LCPs are equivalent to P-LCPs, and grid USOs are equivalent to cube USOs. These results are obtained by showing that both the P-LCP and our $\alpha$-Ham Sandwich variant are equivalent to a new problem we introduce, P-Lin-Bellman. This problem can be seen as a new tool for formulating problems as P-LCPs., Comment: 29 pages, 9 figures

During the diagnostic process, doctors incorporate multimodal information including imaging and the medical history - and similarly medical AI development has increasingly become multimodal. In this paper we tackle a more subtle challenge: doctors take a targeted medical history to obtain only the most pertinent pieces of information; how do we enable AI to do the same? We develop a wrapper method named MINT (Make your model INTeractive) that automatically determines what pieces of information are most valuable at each step, and ask for only the most useful information. We demonstrate the efficacy of MINT wrapping a skin disease prediction model, where multiple images and a set of optional answers to $25$ standard metadata questions (i.e., structured medical history) are used by a multi-modal deep network to provide a differential diagnosis. We show that MINT can identify whether metadata inputs are needed and if so, which question to ask next. We also demonstrate that when collecting multiple images, MINT can identify if an additional image would be beneficial, and if so, which type of image to capture. We showed that MINT reduces the number of metadata and image inputs needed by 82% and 36.2% respectively, while maintaining predictive performance. Using real-world AI dermatology system data, we show that needing fewer inputs can retain users that may otherwise fail to complete the system submission and drop off without a diagnosis. Qualitative examples show MINT can closely mimic the step-by-step decision making process of a clinical workflow and how this is different for straight forward cases versus more difficult, ambiguous cases. Finally we demonstrate how MINT is robust to different underlying multi-model classifiers and can be easily adapted to user requirements without significant model re-training., Comment: 15 pages, 7 figures

Schaefer's dichotomy theorem [Schaefer, STOC'78] states that a boolean constraint satisfaction problem (CSP) is polynomial-time solvable if one of six given conditions holds for every type of constraint allowed in its instances. Otherwise, it is NP-complete. In this paper, we analyze boolean CSPs in terms of their topological complexity, instead of their computational complexity. We attach a natural topological space to the set of solutions of a boolean CSP and introduce the notion of projection-universality. We prove that a boolean CSP is projection-universal if and only if it is categorized as NP-complete by Schaefer's dichotomy theorem, showing that the dichotomy translates exactly from computational to topological complexity. We show a similar dichotomy for SAT variants and homotopy-universality., Comment: 18 pages, 1 figure

It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the PPA-completeness of the Ham Sandwich problem [Filos-Ratsikas and Goldberg, STOC'19]. Recently, a variant of the Ham Sandwich problem called $\alpha$-Ham Sandwich has been studied, in which the point sets are guaranteed to be well-separated [Steiger and Zhao, DCG'10]. The complexity of this search problem remains unknown, but it is known to lie in the complexity class UEOPL [Chiu, Choudhary and Mulzer, ICALP'20]. We define the analogue of this well-separability condition in the necklace splitting problem -- a necklace is $n$-separable, if every subset $A$ of the $n$ types of jewels can be separated from the types $[n]\setminus A$ by at most $n$ separator points. By the reduction to the Ham Sandwich problem it follows that this version of necklace splitting has a unique solution. We furthermore provide two FPT algorithms: The first FPT algorithm solves 2-Thief-Necklace-Splitting on $(n-1+\ell)$-separable necklaces with $n$ types of jewels and $m$ total jewels in time $2^{O(\ell\log\ell)}+m^2$. In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on $n$-separable necklaces. Thus, attempts to show hardness of $\alpha$-Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests $(n-1+\ell)$-separability of a given necklace with $n$ types of jewels in time $2^{O(\ell^2)}\cdot n^4$. In particular, $n$-separability can thus be tested in polynomial time, even though testing well-separation of point sets is coNP-complete [Bergold et al., SWAT'22]., Comment: 16 pages, 7 figures

We solve a problem of Dujmovi\'c and Wood (2007) by showing that a complete convex geometric graph on $n$ vertices cannot be decomposed into fewer than $n-1$ star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

For any positive edge density $p$, a random graph in the Erd\H{o}s-Renyi $G_{n,p}$ model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability $\rho(n)$, such that for any distribution $\mathcal{G}$ (in this model) on graphs with $n$ vertices in which each potential edge has a marginal probability of being present at least $\rho(n)$, a graph drawn from $\mathcal{G}$ is connected with non-zero probability? As it turns out, the condition ``edges that do not share endpoints are independent'' needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold $\rho(n)$. For each condition, we provide upper and lower bounds for $\rho(n)$. In the strongest condition, the coloring model (which includes, e.g., random geometric graphs), we show that $\rho(n)\rightarrow 2-\phi\approx 0.38$ for $n\rightarrow\infty$, proving a conjecture by Badakhshian, Falgas-Ravry, and Sharifzadeh. This separates the coloring models from the weaker independence conditions we consider, as there we prove that $\rho(n)>0.5-o(n)$. In stark contrast to the coloring model, for our weakest independence condition -- pairwise independence of non-adjacent edges -- we show that $\rho(n)$ lies within $O(1/n^2)$ of the threshold $1-2/n$ for completely arbitrary distributions., Comment: 35 pages, 6 figures. [v2] adds related work and is intended as a full version accompanying the version to appear at RANDOM'23

Optical flow provides information on relative motion that is an important component in many computer vision pipelines. Neural networks provide high accuracy optical flow, yet their complexity is often prohibitive for application at the edge or in robots, where efficiency and latency play crucial role. To address this challenge, we build on the latest developments in event-based vision and spiking neural networks. We propose a new network architecture, inspired by Timelens, that improves the state-of-the-art self-supervised optical flow accuracy when operated both in spiking and non-spiking mode. To implement a real-time pipeline with a physical event camera, we propose a methodology for principled model simplification based on activity and latency analysis. We demonstrate high speed optical flow prediction with almost two orders of magnitude reduced complexity while maintaining the accuracy, opening the path for real-time deployments., Comment: Accepted for IEEE CVPRW, Vancouver 2023. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media. Copyright 2023 IEEE

We study the problem of recognizing whether a given abstract simplicial complex $K$ is the $k$-skeleton of the nerve of $j$-dimensional convex sets in $\mathbb{R}^d$. We denote this problem by $R(k,j,d)$. As a main contribution, we unify the results of many previous works under this framework and show that many of these works in fact imply stronger results than explicitly stated. This allows us to settle the complexity status of $R(1,j,d)$, which is equivalent to the problem of recognizing intersection graphs of $j$-dimensional convex sets in $\mathbb{R}^d$, for any $j$ and $d$. Furthermore, we point out some trivial cases of $R(k,j,d)$, and demonstrate that $R(k,j,d)$ is ER-complete for $j\in\{d-1,d\}$ and $k\geq d$., Comment: 6 pages, 1 figure, presented at EuroCG'23

Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of data points. Under projective duality, this can be interpreted as a depth measure for query points with respect to an arrangement of data hyperplanes. The study of depth measures for query points with respect to a set of data points has a long history, and many such depth measures have natural counterparts in the setting of hyperplane arrangements. For example, regression depth is the counterpart of Tukey depth. Motivated by this, we study general families of depth measures for hyperplane arrangements and show that all of them must have a deep point. Along the way we prove a Tverberg-type theorem for hyperplane arrangements, giving a positive answer to a conjecture by Rousseeuw and Hubert from 1999. We also get three new proofs of the centerpoint theorem for regression depth, all of which are either stronger or more general than the original proof by Amenta, Bern, Eppstein, and Teng. Finally, we prove a version of the center transversal theorem for regression depth., Comment: To be presented at the 39th International Symposium on Computational Geometry (SoCG 2023)

Purpose: Automated distinct bone segmentation from CT scans is widely used in planning and navigation workflows. U-Net variants are known to provide excellent results in supervised semantic segmentation. However, in distinct bone segmentation from upper body CTs a large field of view and a computationally taxing 3D architecture are required. This leads to low-resolution results lacking detail or localisation errors due to missing spatial context when using high-resolution inputs. Methods: We propose to solve this problem by using end-to-end trainable segmentation networks that combine several 3D U-Nets working at different resolutions. Our approach, which extends and generalizes HookNet and MRN, captures spatial information at a lower resolution and skips the encoded information to the target network, which operates on smaller high-resolution inputs. We evaluated our proposed architecture against single resolution networks and performed an ablation study on information concatenation and the number of context networks. Results: Our proposed best network achieves a median DSC of 0.86 taken over all 125 segmented bone classes and reduces the confusion among similar-looking bones in different locations. These results outperform our previously published 3D U-Net baseline results on the task and distinct-bone segmentation results reported by other groups. Conclusion: The presented multi-resolution 3D U-Nets address current shortcomings in bone segmentation from upper-body CT scans by allowing for capturing a larger field of view while avoiding the cubic growth of the input pixels and intermediate computations that quickly outgrow the computational capacities in 3D. The approach thus improves the accuracy and efficiency of distinct bone segmentation from upper-body CT., Comment: Under submission

A family of $k$ point sets in $d$ dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong assumption that allows us to conclude that certain kinds of generalized ham-sandwich cuts for the point sets exist. But how hard is it to check if a given family of high-dimensional point sets has this property? Starting from this question, we study several algorithmic aspects of the existence of transversals and separations in high-dimensions. First, we give an explicit proof that $k$ point sets are well-separated if and only if their convex hulls admit no $(k - 2)$-transversal, i.e., if there exists no $(k - 2)$-dimensional flat that intersects the convex hulls of all $k$ sets. It follows that the task of checking well-separation lies in the complexity class coNP. Next, we show that it is NP-hard to decide whether there is a hyperplane-transversal (that is, a $(d - 1)$-transversal) of a family of $d + 1$ line segments in $\mathbb{R}^d$, where $d$ is part of the input. As a consequence, it follows that the general problem of testing well-separation is coNP-complete. Furthermore, we show that finding a hyperplane that maximizes the number of intersected sets is NP-hard, but allows for an $\Omega\left(\frac{\log k}{k \log \log k}\right)$-approximation algorithm that is polynomial in $d$ and $k$, when each set consists of a single point. When all point sets are finite, we show that checking whether there exists a $(k - 2)$-transversal is in fact strongly NP-complete., Comment: 14 pages, 1 figure; a preliminary version appeared in SWAT 2022

Purpose: The localisation and segmentation of individual bones is an important preprocessing step in many planning and navigation applications. It is, however, a time-consuming and repetitive task if done manually. This is true not only for clinical practice but also for the acquisition of training data. We therefore not only present an end-to-end learnt algorithm that is capable of segmenting 125 distinct bones in an upper-body CT, but also provide an ensemble-based uncertainty measure that helps to single out scans to enlarge the training dataset with. Methods We create fully automated end-to-end learnt segmentations using a neural network architecture inspired by the 3D-Unet and fully supervised training. The results are improved using ensembles and inference-time augmentation. We examine the relationship of ensemble-uncertainty to an unlabelled scan's prospective usefulness as part of the training dataset. Results: Our methods are evaluated on an in-house dataset of 16 upper-body CT scans with a resolution of \SI{2}{\milli\meter} per dimension. Taking into account all 125 bones in our label set, our most successful ensemble achieves a median dice score coefficient of 0.83. We find a lack of correlation between a scan's ensemble uncertainty and its prospective influence on the accuracies achieved within an enlarged training set. At the same time, we show that the ensemble uncertainty correlates to the number of voxels that need manual correction after an initial automated segmentation, thus minimising the time required to finalise a new ground truth segmentation. Conclusion: In combination, scans with low ensemble uncertainty need less annotator time while yielding similar future DSC improvements. They are thus ideal candidates to enlarge a training set for upper-body distinct bone segmentation from CT scans. }

Diagnosing and mitigating changes in model fairness under distribution shift is an important component of the safe deployment of machine learning in healthcare settings. Importantly, the success of any mitigation strategy strongly depends on the structure of the shift. Despite this, there has been little discussion of how to empirically assess the structure of a distribution shift that one is encountering in practice. In this work, we adopt a causal framing to motivate conditional independence tests as a key tool for characterizing distribution shifts. Using our approach in two medical applications, we show that this knowledge can help diagnose failures of fairness transfer, including cases where real-world shifts are more complex than is often assumed in the literature. Based on these results, we discuss potential remedies at each step of the machine learning pipeline.

Recently, the second and third author showed that complete geometric graphs on $2n$ vertices in general cannot be partitioned into $n$ plane spanning trees. Building up on this work, in this paper, we initiate the study of partitioning into beyond planar subgraphs, namely into $k$-planar and $k$-quasi-planar subgraphs and obtain first bounds on the number of subgraphs required in this setting.

Assume you have a 2-dimensional pizza with $2n$ ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, that is, your friend and you should each get exactly half of each ingredient. How many cuts do you need? It was recently shown using topological methods that $n$ cuts always suffice. In this work, we study the computational complexity of finding such $n$ cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets $n$ cuts suffice, which does not use any topological methods. We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated., Comment: 14 pages, 4 figures

Let $P$ be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in $P$. We say two points $a,b\in P$ can see each other if the line segment $seg(a,b)$ is contained in $P$. We denote by $V(P)$ the family of all minimum guard placements. The Hausdorff distance makes $V(P)$ a metric space and thus a topological space. We show homotopy-universality, that is for every semi-algebraic set $S$ there is a polygon $P$ such that $V(P)$ is homotopy equivalent to $S$. Furthermore, for various concrete topological spaces $T$, we describe instances $I$ of the art gallery problem such that $V(I)$ is homeomorphic to $T$., Comment: 32 pages, 36 figures. For associated GeoGebra files, see source files. For associated video, see http://youtube.com/playlist?list=PLh3Niobwkd8pZcSF_Al7e2eeZ-8vqNm-b . Version v2 adds some additional details and references to publications that appeared after v1

The Tukey depth of a flat with respect to a point set is a concept that appears in many areas of discrete and computational geometry. In particular, the study of centerpoints, center transversals, Ham Sandwich cuts, or $k$-edges can all be phrased in terms of depths of certain flats with respect to one or more point sets. In this work, we introduce the Tukey depth histogram of $k$-flats in $\mathbb{R}^d$ with respect to a point set $P$, which is a vector $D^{k,d}(P)$, whose $i$'th entry $D^{k,d}_i(P)$ denotes the number of $k$-flats spanned by $k+1$ points of $P$ that have Tukey depth $i$ with respect to $P$. As our main result, we give a complete characterization of the depth histograms of points, that is, for any dimension $d$ we give a description of all possible histograms $D^{0,d}(P)$. This then allows us to compute the exact number of possible such histograms.

We study families of depth measures defined by natural sets of axioms. We show that any such depth measure is a constant factor approximation of Tukey depth. We further investigate the dimensions of depth regions, showing that the Cascade conjecture, introduced by Kalai for Tverberg depth, holds for all depth measures which satisfy our most restrictive set of axioms, which includes Tukey depth. Along the way, we introduce and study a new depth measure called enclosing depth, which we believe to be of independent interest, and show its relation to a constant-fraction Radon theorem on certain two-colored point sets.

Countless low-surface brightness objects - including spiral galaxies, dwarf galaxies, and noise patterns - have been detected in recent large surveys. Classically, astronomers visually inspect those detections to distinguish between real low-surface brightness galaxies and artefacts. Employing the Dark Energy Survey (DES) and machine learning techniques, Tanoglidis et al. (2020) have shown how this task can be automatically performed by computers. Here, we build upon their pioneering work and further separate the detected low-surface brightness galaxies into spirals, dwarf ellipticals, and dwarf irregular galaxies. For this purpose, we have manually classified 5567 detections from multi-band images from DES and searched for a neural network architecture capable of this task. Employing a hyperparameter search, we find a family of convolutional neural networks achieving similar results as with the manual classification, with an accuracy of 85% for spiral galaxies, 94% for dwarf ellipticals, and 52% for dwarf irregulars. For dwarf irregulars - due to their diversity in morphology - the task is difficult for humans and machines alike. Our simple architecture shows that machine learning can reduce the workload of astronomers studying large data sets by orders of magnitudes, as will be available in the near future with missions such as Euclid., Comment: 8 pages, 6 figures, 1 table, accepted for publication in The Open Journal of Astrophysics. The code can be found on GitLab: https://gitlab.com/VoltarCH/deeplearning_des