In computational geometry, the construction of essential primitives like convex hulls, Voronoi diagrams and Delaunay triangulations require the evaluation of the signs of determinants, which are sums of products. The same signs are needed for the exa
ct solution of linear programming problems and systems of linear inequalities. Computing these signs exactly with inexact floating point arithmetic is challenging, and we present yet another algorithm for this task. Our algorithm is efficient and uses only of floating point arithmetic, which is much faster than exact arithmetic. We prove that the algorithm is correct and provide efficient and tested C++ code for it.
Geometric graphs form an important family of hidden structures behind data. In this paper, we develop an efficient and robust algorithm to infer a graph skeleton behind a point cloud data (PCD)embedded in high dimensional space. Previously, there has
been much work to recover a hidden graph from a low-dimensional density field, or from a relatively clean high-dimensional PCD (in the sense that the input points are within a small bounded distance to a true hidden graph). Our proposed approach builds upon the recent line of work on using a persistence-guided discrete Morse (DM) theory based approach to reconstruct a geometric graph from a density field defined over a triangulation of low-dimensional Euclidean domain. In particular, we first give a very simple generalization of this DM-based algorithm from a density-function perspective to a general filtration perspective. On the theoretical front, we show that the output of the generalized algorithm contains a so-called lexicographic-optimal persistent cycle basis w.r.t the input filtration, justifying that the output is indeed meaningful. On the algorithmic front, this generalization allows us to use the idea of sparsified weighted Rips filtration (developed by Buchet etal) to develop a new graph reconstruction algorithm for noisy point cloud data (PCD) (which do not need to be embedded). The new algorithm is robust to background noise and non-uniform distribution of input points. We provide various experimental results to show the efficiency and effectiveness of our new graph reconstruction algorithm for PCDs.
We present subquadratic algorithms in the algebraic decision-tree model for several textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segment
s in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $Deltain C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $Delta$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/log^2n)log^{O(1)}log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+varepsilon})$, for any $varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the emph{order type} of the lines, a handicap that turns out to be beneficial for speeding up our algorithm.
Given two sets $S$ and $T$ of points in the plane, of total size $n$, a {many-to-many} matching between $S$ and $T$ is a set of pairs $(p,q)$ such that $pin S$, $qin T$ and for each $rin Scup T$, $r$ appears in at least one such pair. The {cost of a
pair} $(p,q)$ is the (Euclidean) distance between $p$ and $q$. In the {minimum-cost many-to-many matching} problem, the goal is to compute a many-to-many matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimum-weight edge cover in a bipartite graph, and hence can be solved in $O(n^3)$ time. In a more restricted setting where all the points are on a line, the problem can be solved in $O(nlog n)$ time [Colannino, Damian, Hurtado, Langerman, Meijer, Ramaswami, Souvaine, Toussaint; Graphs Comb., 2007]. However, no progress has been made in the general planar case in improving the cubic time bound. In this paper, we obtain an $O(n^2cdot poly(log n))$ time exact algorithm and an $O( n^{3/2}cdot poly(log n))$ time $(1+epsilon)$-approximation in the planar case. Our results affirmatively address an open problem posed in [Colannino et al., Graphs Comb., 2007].
We present a method for the automatic assembly of apictorial jigsaw puzzles. This method relies on integral area invariants for shape matching and an optimization process to aggregate shape matches into a final puzzle assembly. Assumptions about indi
vidual piece shape or arrangement are not necessary. We illustrate our method by solving example puzzles of various shapes and sizes.
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, t
hat 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.
Tusnadys problem asks to bound the discrepancy of points and axis-parallel boxes in $mathbb{R}^d$. Algorithmic bounds on Tusnadys problem use a canonical decomposition of Matouv{s}ek for the system of points and axis-parallel boxes, together with oth
er techniques like partial coloring and / or random-walk based methods. We use the notion of emph{shallow cell complexity} and the emph{shallow packing lemma}, together with the chaining technique, to obtain an improved decomposition of the set system. Coupled with an algorithmic technique of Bansal and Garg for discrepancy minimization, which we also slightly extend, this yields improved algorithmic bounds on Tusnadys problem. For $dgeq 5$, our bound matches the lower bound of $Omega(log^{d-1}n)$ given by Matouv{s}ek, Nikolov and Talwar [IMRN, 2020] -- settling Tusnadys problem, upto constant factors. For $d=2,3,4$, we obtain improved algorithmic bounds of $O(log^{7/4}n)$, $O(log^{5/2}n)$ and $O(log^{13/4}n)$ respectively, which match or improve upon the non-constructive bounds of Nikolov for $dgeq 3$. Further, we also give improved bounds for the discrepancy of set systems of points and polytopes in $mathbb{R}^d$ generated via translations of a fixed set of hyperplanes. As an application, we also get a bound for the geometric discrepancy of anchored boxes in $mathbb{R}^d$ with respect to an arbitrary measure, matching the upper bound for the Lebesgue measure, which improves on a result of Aistleitner, Bilyk, and Nikolov [MC and QMC methods, emph{Springer, Proc. Math. Stat.}, 2018] for $dgeq 4$.
We present sweeping line graphs, a generalization of $Theta$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use
general inductive arguments to make the step to the constrained setting that could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.
Let $p(m)$ (respectively, $q(m)$) be the maximum number $k$ such that any tree with $m$ edges can be transformed by contracting edges (respectively, by removing vertices) into a caterpillar with $k$ edges. We derive closed-form expressions for $p(m)$
and $q(m)$ for all $m ge 1$. The two functions $p(n)$ and $q(n)$ can also be interpreted in terms of alternating paths among $n$ disjoint line segments in the plane, whose $2n$ endpoints are in convex position.
This is the arXiv index for the electronic proceedings of GD 2021, which contains the peer-reviewed and revised accepted papers with an optional appendix. Proceedings (without appendices) are also to be published by Springer in the Lecture Notes in Computer Science series.
