We revisit a classical problem in computational geometry: finding the largest-volume axis-aligned empty box (inside a given bounding box) amidst n given points in d dimensions. Previously, the best algorithms known have running time O(n log^2 n) for d = 2 (by Aggarwal and Suri [SoCG'87]) and near n^d for d >= 3. We describe faster algorithms with running time

- O(n 2^{O(log^*n)} log n) for d = 2,
- O(n^{2.5+o(1)}) time for d = 3, and
- O~(n^{(5d+2)/6}) time for any constant d >= 4.

Given a set of n points in the plane, and a parameter k, we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing k points. We present the first near quadratic time algorithm for this problem, improving over the previous near-O(n^{5/2})-time algorithm by Kaplan et al. [ESA 2017]. We provide an almost matching conditional lower bound, under the assumption that (min,+)-convolution cannot be solved in truly subquadratic time. Furthermore, we present a new reduction (for either perimeter or area) that can make the time bound sensitive to k, giving near O(nk) time. We also present a near linear time (1+eps)-approximation algorithm to the minimum area of the optimal rectangle containing k points. In addition, we study related problems including the 3-sided, arbitrarily oriented, weighted, and subset sum versions of the problem.

- arxiv version
- Discrete and Computational Geometry, 66(2):769-791, 2021
- In Proc. 35th International Symposium on Computational Geometry (SoCG), pages 23:1-23:15, 2019

At SODA'93, Chazelle and Matousek presented a derandomization of Clarkson's sampling-based algorithm for solving linear programs with n constraints and d variables in d^{(7+o(1))d} n deterministic time. The time bound can be improved to d^{(5+o(1))d} n with subsequent work by Bronnimann, Chazelle, and Matousek [FOCS'93]. We first point out a much simpler derandomization of Clarkson's algorithm that avoids epsilon-approximations and runs in d^{(3+o(1))d} n time. We then describe a few additional ideas that eventually improve the deterministic time bound to d^{(1/2+o(1))d} n.

- PDF file
- PDF talk slides
- ACM Transactions of Algorithms, 14(3): 30:1-30:10, 2018 (SODA special issue)
- In Proc. 27th ACM-SIAM Symposium on Discrete Algorithms, pages 1213-1219, 2016

We present three results related to dynamic convex hulls:

- A fully dynamic data structure for maintaining a set of n points in the plane so that we can find the edges of the convex hull intersecting a query line, with expected query and amortized update time O(log^{1+eps}n) for an arbitrarily small constant eps>0. This improves the previous bound of O(log^{3/2}n).
- A fully dynamic data structure for maintaining a set of n points in the plane to support halfplane range reporting queries in O(log n + k) time with O(polylog n) expected amortized update time. A similar result holds for 3-dimensional orthogonal range reporting. For 3-dimensional halfspace range reporting, the query time increases to O(log^2 n/loglog n + k).
- A semi-online dynamic data structure for maintaining a set of n line segments in the plane, so that we can decide whether a query line segment lies completely above the lower envelope, with query time O(log n) and amortized update time O(n^eps). As a corollary, we can solve the following problem in O(n^{1+eps}) time: given a triangulated terrain in 3-d of size n, identify all faces that are partially visible from a fixed viewpoint.

- PDF file
- PDF talk slides
- International Journal of Computational Geometry and Applications, 22:341-364, 2012 (SoCG special issue)
- In
*Proc. 27th ACM Symposium on Computational Geometry (SoCG)*, pages 27-36, 2011

We initiate the study of exact geometric algorithms that require limited storage and make only a small number of passes over the input. Fundamental problems such as low-dimensional linear programming and convex hulls are considered.

- PostScript file
- Discrete and Computational Geometry, 37:79-102, 2007 (SoCG special issue)
- In Proc. 21st ACM Symposium on Computational Geometry (SoCG), pages 180-189, 2005

Given a parametric graph with n vertices and m edges where edge weights change linearly over time, we show how to find the time value at which the heaviest edge weight in the minimum spanning tree is minimized in O(n(m/n)^epsilon log n + m) expected time...

We give three related algorithmic results concerning a simple polygon P:

- Continuing previous efforts by Bespamyatnikh, Biedl, Bose, Czyzowicz, E. Demaine, M. Demaine, Kim, Kranakis, Lubiw, Maheshwari, Morin, Shin, Toussaint, Vigneron, and Yang, we show how to find a largest pair of disjoint congruent disks inside P in linear expected time.
- As a subroutine for the above result, we show how to find the convex hull of any given subset of the vertices of P in linear worst-case time.
- More generally, we show how to compute a triangulation of any given subset of the vertices or edges of P in almost linear time.

- PostScript file (9/04 version)
- Computational Geometry: Theory and Applications, 35:209-217, 2006
- (The main open question about the third problem was solved by van Kreveld, Loeffler, and Mitchell (2008).)

We present the first optimal algorithm to compute the maximum
*Tukey depth* (also known as *location* or *halfspace
depth*) for
a non-degenerate point set in the plane. The algorithm is randomized
and requires O(n log n) expected time for n data points. In a
higher fixed dimension d >= 3, the expected time bound is
O(n^{d-1}), which is probably optimal as well. The result is
obtained using an interesting variant of the author's
randomized
optimization technique, capable of solving "implicit"
linear-programming-type problems; some other applications of this
technique are briefly mentioned.

Applications in the plane include improved algorithms for finding a line that misclassifies the fewest among a set of bichromatic points, and finding the smallest circle enclosing all but k points. We also discuss related problems of finding local minima in levels.

- Gzipped postscript file | PDF file
- SIAM Journal on Computing, 34:879-893, 2005
- In Proc. 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 570-579, 2002

- Postscript file
- Discrete & Computational Geometry, 22:547-567, 1999 (SoCG special issue)
- In Proc. 14th ACM Symposium on Computational Geometry (SoCG), pages 269-278, 1998

- Postscript file
- Journal of Algorithms, 27:147-166, 1998
- Preliminary version in Proc. 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 464-472, 1997

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Timothy Chan (Last updated Aug 2023)