More Like this

1. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model

   https://doi.org/10.4230/LIPIcs.ISAAC.2021.3  

   Aronov, Boris; de_Berg, Mark; Cardinal, Jean; Ezra, Esther; Iacono, John; Sharir, Micha (November 2021, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ahn, Hee-Kap Ahn; Sadakane, Kunihiko (Ed.)

   We present subquadratic algorithms in the algebraic decision-tree model for several 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 segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ ∈ C, the number of intersection points between the segments of A and those of B that lie in Δ. 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²/log²n) log^O(1) log n) time. We present solutions in the algebraic decision-tree model whose cost is O(n^{60/31+ε}), for any ε > 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 order type of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm. 

   more » « less
2. A Comparison of Tree Search Method for Graph Topology Design Problems

   Short, Ada-Rhodes; DuPont, B.; Campbell, M.I. (July 2018, International Conference on Design Computing And Cognition (DCC'18 or DCC18))

   In this paper, we discuss the relevance and effectiveness of two com-mon methods for searching decision trees that represent design problems. When design problems are encoded in decision trees they are of-ten multimodal, capture a range of complexity in valid solutions, and have distinguishable internal locations. We propose the use of a simple Color Graph problem to represent these characteristics. The two methods evaluated are a genetic algorithm and a Monte Carlo tree search. Using the Color Graph problem, it is demonstrated that a genetic algorithm can perform exceptionally well on such unbounded and opaque design decision trees and that Monte Carlo tree searches are ineffective. Insights from this experiment are used to draw conclusions about the nature of design problems stored in decision trees and the need for new methods to search such trees and lead us to believe that exploitative methods are more effective than rigorously explorative methods. 

   more » « less
3. A General Technique for Searching in Implicit Sets via Function Inversion

   https://doi.org/10.1137/1.9781611977936.20  

   Aronov, Boris; Cardinal, Jean; Dallant, Justin; Iacono, John (January 2024, SIAM)

   Given a function f from the set [N] to a d-dimensional integer grid, we consider data structures that allow efficient orthogonal range searching queries in the image of f, without explicitly storing it. We show that, if f is of the form [N] → [2w]d for some w = polylog(N) and is computable in constant time, then, for any 0 < α < 1, we can obtain a data structure using Õ(N1-α/3) words of space such that, for a given d-dimensional axis-aligned box B, we can search for some x ∈ [N] such that f (x) ∈ B in time Õ(Nα). This result is obtained simply by combining integer range searching with the Fiat-Naor function inversion scheme, which was already used in data-structure problems previously. We further obtain • data structures for range counting and reporting, predecessor, selection, ranking queries, and combinations thereof, on the set f ([N]), • data structures for preimage size and preimage selection queries for a given value of f, and • data structures for selection and ranking queries on geometric quantities computed from tuples of points in d-space. These results unify and generalize previously known results on 3SUM-indexing and string searching, and are widely applicable as a black box to a variety of problems. In particular, we give a data structure for a generalized version of gapped string indexing, and show how to preprocess a set of points on an integer grid in order to efficiently compute (in sublinear time), for points contained in a given axis-aligned box, their Theil-Sen estimator, the kth largest area triangle, or the induced hyperplane that is the kth furthest from the origin. 

   more » « less
4. Optimal Euclidean Tree Covers

   https://doi.org/10.4230/LIPIcs.SoCG.2024.37  

   Chang, Hsien-Chih; Conroy, Jonathan; Le, Hung; Milenković, Lazar; Solomon, Shay; Than, Cuong (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   A (1+e)-stretch tree cover of a metric space is a collection of trees, where every pair of points has a (1+e)-stretch path in one of the trees. The celebrated Dumbbell Theorem [Arya et al. STOC'95] states that any set of n points in d-dimensional Euclidean space admits a (1+e)-stretch tree cover with O_d(e^{-d} ⋅ log(1/e)) trees, where the O_d notation suppresses terms that depend solely on the dimension d. The running time of their construction is O_d(n log n ⋅ log(1/e)/e^d + n ⋅ e^{-2d}). Since the same point may occur in multiple levels of the tree, the maximum degree of a point in the tree cover may be as large as Ω(log Φ), where Φ is the aspect ratio of the input point set. In this work we present a (1+e)-stretch tree cover with O_d(e^{-d+1} ⋅ log(1/e)) trees, which is optimal (up to the log(1/e) factor). Moreover, the maximum degree of points in any tree is an absolute constant for any d. As a direct corollary, we obtain an optimal {routing scheme} in low-dimensional Euclidean spaces. We also present a (1+e)-stretch Steiner tree cover (that may use Steiner points) with O_d(e^{(-d+1)/2} ⋅ log(1/e)) trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive O_d(n log n) term; this improves over the running time underlying the Dumbbell Theorem. 

   more » « less
5. Rare-event Simulation for Neural Network and Random Forest Predictors

   https://doi.org/10.1145/3519385  

   Bai, Yuanlu; Huang, Zhiyuan; Lam, Henry; Zhao, Ding (July 2022, ACM Transactions on Modeling and Computer Simulation)

   We study rare-event simulation for a class of problems where the target hitting sets of interest are defined via modern machine learning tools such as neural networks and random forests. This problem is motivated from fast emerging studies on the safety evaluation of intelligent systems, robustness quantification of learning models, and other potential applications to large-scale simulation in which machine learning tools can be used to approximate complex rare-event set boundaries. We investigate an importance sampling scheme that integrates the dominating point machinery in large deviations and sequential mixed integer programming to locate the underlying dominating points. Our approach works for a range of neural network architectures including fully connected layers, rectified linear units, normalization, pooling and convolutional layers, and random forests built from standard decision trees. We provide efficiency guarantees and numerical demonstration of our approach using a classification model in the UCI Machine Learning Repository. 

   more » « less