9,212 research outputs found
Dynamic Geometric Data Structures via Shallow Cuttings
No full textWe present new results on a number of fundamental problems about dynamic geometric data structures:
1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n^{11/12} for (i) and (ii), n^{7/8} for (iii) and (iv), and n^{2/3} for (v). Previously, sublinear bounds were known only for restricted "semi-online" settings [Chan, SODA 2002].
2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O(log^2n), and the amortized update time is O(log^4n) instead of O(log^5n) [Chan, SODA 2006; Kaplan et al., SODA 2017].
3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O(log^4n) instead of O(log^7n) [Eppstein 1995; Chan, SODA 2006; Kaplan et al., SODA 2017]
Tree Drawings Revisited
No full textWe make progress on a number of open problems concerning the area requirement for drawing trees on a grid. We prove that
1) every tree of size n (with arbitrarily large degree) has a straight-line drawing with area n2^{O(sqrt{log log n log log log n})}, improving the longstanding O(n log n) bound;
2) every tree of size n (with arbitrarily large degree) has a straight-line upward drawing with area n sqrt{log n}(log log n)^{O(1)}, improving the longstanding O(n log n) bound;
3) every binary tree of size n has a straight-line orthogonal drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Shin, Kim, and Chwa (1996) and Chan, Goodrich, Kosaraju, and Tamassia (1996);
4) every binary tree of size n has a straight-line order-preserving drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Garg and Rusu (2003);
5) every binary tree of size n has a straight-line orthogonal order-preserving drawing with area n2^{O(sqrt{log n})}, improving the O(n^{3/2}) previous bound by Frati (2007)
Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back
No full textWe revisit the orthogonal range searching problem and the exact l_infinity nearest neighbor searching problem for a static set of n points when the dimension d is moderately large. We give the first data structure with near linear space that achieves truly sublinear query time when the dimension is any constant multiple of log n. Specifically, the preprocessing time and space are O(n^{1+delta}) for any constant delta>0, and the expected query time is n^{1-1/O(c log c)} for d = c log n. The data structure is simple and is based on a new "augmented, randomized, lopsided" variant of k-d trees. It matches (in fact, slightly improves) the performance of previous combinatorial algorithms that work only in the case of offline queries [Impagliazzo, Lovett, Paturi, and Schneider (2014) and Chan (SODA'15)]. It leads to slightly faster combinatorial algorithms for all-pairs shortest paths in general real-weighted graphs and rectangular Boolean matrix multiplication.
In the offline case, we show that the problem can be reduced to the Boolean orthogonal vectors problem and thus admits an n^{2-1/O(log c)}-time non-combinatorial algorithm [Abboud, Williams, and Yu (SODA'15)]. This reduction is also simple and is based on range trees.
Finally, we use a similar approach to obtain a small improvement to Indyk's data structure [FOCS'98] for approximate l_infinity nearest neighbor search when d = c log n
Dataset for Settling behaviour of thin curved particles in quiescent fluid and turbulence
No full textThis dataset contains the experimental data and a MATLAB script that enables the reproduction of the figures in: Timothy T.K. Chan, Luis Blay Esteban, Sander G. Huisman, John Shrimpton and Bharathram Ganapathisubramani. Settling behaviour of thin curved particles in quiescent fluid and turbulence. Journal of Fluid Mechanics.
DOI: 10.1017/jfm.2021.520
Data.mat contains three structures: 'Quiescent', 'Turb', and 'PIV'. They represent data of the quiescent cases, the turbulent cases, and PIV respectively. The list below documents the contents of 'Quiescent and 'Turb'. Unless otherwise specified, these fields are present in 'Quiescent' and 'Turb'.
</span
More on Change-Making and Related Problems
No full textGiven a set of n integer-valued coin types and a target value t, the well-known change-making problem asks for the minimum number of coins that sum to t, assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j, for every j = 0,…,t. For example, the textbook dynamic programming algorithms can solve the all-targets problem in O(nt) time. Recently, Chan and He (SOSA'20) described a number of O(t polylog t)-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version.
In this paper, we obtain a number of new results on change-making and related problems:
- We present a new algorithm for the all-targets change-making problem with running time Õ(t^{4/3}), improving a previous Õ(t^{3/2})-time algorithm.
- We present a very simple Õ(u²+t)-time algorithm for the all-targets change-making problem, where u denotes the maximum coin value. The analysis of the algorithm uses a theorem of Erdős and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities version of the unbounded knapsack problem (for integer item weights bounded by u).
- For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He’s algorithms that runs in Õ(u) time (instead of Õ(t)).
- For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in Õ(nu) time, improving previous near-u²-time algorithms.
- We also observe how one of our ideas implies a new result on the minimum word break problem, an optimization version of a string problem studied by Bringmann et al. (FOCS'17), generalizing change-making (which corresponds to the unary special case)
<i>Science Translational Medicine</i> Podcast: 23 March 2011
No full textA conversation with Timothy Chan about a new way to predict breast cancer metastasis.</jats:p
A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions
No full textChazelle [FOCS'89] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same
Minimum L_∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee’s Measure Problem
No full textWe present a (combinatorial) algorithm with running time close to O(n^d) for computing the minimum directed L_∞ Hausdorff distance between two sets of n points under translations in any constant dimension d. This substantially improves the best previous time bound near O(n^{5d/4}) by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan’s algorithm [FOCS'13] for Klee’s measure problem.
To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to Ω(n^d) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis
Dynamic Streaming Algorithms for Epsilon-Kernels
No full textIntroduced by Agarwal, Har-Peled, and Varadarajan [J. ACM, 2004], an epsilon-kernel of a point set is a coreset that can be used to approximate the width, minimum enclosing cylinder, minimum bounding box, and solve various related geometric optimization problems. Such coresets form one of the most important tools in the design of linear-time approximation algorithms in computational geometry, as well as efficient insertion-only streaming algorithms and dynamic (non-streaming) data structures. In this paper, we continue the theme and explore dynamic streaming algorithms (in the so-called turnstile model).
Andoni and Nguyen [SODA 2012] described a dynamic streaming algorithm for maintaining a (1+epsilon)-approximation of the width using O(polylog U) space and update time for a point set in [U]^d for any constant dimension d and any constant epsilon>0. Their sketch, based on a "polynomial method", does not explicitly maintain an epsilon-kernel. We extend their method to maintain an epsilon-kernel, and at the same time reduce some of logarithmic factors. As an application, we obtain the first randomized dynamic streaming algorithm for the width problem (and related geometric optimization problems) that supports k outliers, using poly(k, log U) space and time
Approximation Schemes for 0-1 Knapsack
No full textWe revisit the standard 0-1 knapsack problem. The latest polynomial-time approximation scheme by Rhee (2015) with approximation factor 1+eps has running time near O(n+(1/eps)^{5/2}) (ignoring polylogarithmic factors), and is randomized. We present a simpler algorithm which achieves the same result and is deterministic.
With more effort, our ideas can actually lead to an improved time bound near O(n + (1/eps)^{12/5}), and still further improvements for small n
- …
