We study the problem of minimizing the area of the convex hull of k polygons with a total of n vertices in the plane, under translations and rigid motions for any fixed k ≥ 3. For any ε ∈ (0, 1), we give (1 + ε)-approximation algorithms running in O(ε^{-1/2} log n + ε^{1/2 - k}) time for translations, and in O(ε^{-1/2} log n + ε^{3/2 - 2k}) time for rigid motions. We also consider minimizing the perimeter of the convex hull under translations and obtain a (1 + ε)-approximation algorithm running in O(ε^{-1/2} log n + ε^{1/2 - k}log^{k-1}(1/ε)) time. To the best of our knowledge, these are the first results of this kind for k ≥ 3 polygons. Furthermore, for the special case of two polygons with n₀ and n₁ vertices (n₀ ≥ n₁), respectively, we give an O(n₀+n₁log²(n₀+n₁))-time algorithm for the minimum-perimeter problem. This significantly improves upon the best-known O((n₀+n₁)log²(n₀+n₁)) bound by eliminating the logarithmic overhead associated with the larger input size n₀.

Given a set of n points in d-dimensional space, each assigned a positive weight, we study the problem of finding k axis-parallel unit hypercubes that maximize the total weight of the points contained in their union. In this paper, we present both exact and (1 - ε)-approximation algorithms for the case of k = 2. We present an exact algorithm that runs in O(n²) time in the plane, improving the previous O(n² log² n)-time result. This algorithm generalizes to higher dimensions and larger k in O(n^{dk/2}) time for fixed d and k. We also present a (1 - ε)-approximation algorithm that runs in O(n log min{n, 1/ε} + 1/ε³) time for k = 2 in the plane, improving the best known result. Our approximation algorithm also extends to higher dimensions.

We study the problem of minimizing the convex hull of two convex polytopes with n vertices in total under translation in d-dimensional space ℝd for any fixed dimension d ≥ 2. For d ≥ 2, we present a deterministic O (n )-time algorithm returning a translation minimizing the area of the convex hull, improving upon the previously best O (n log n )-time algorithm. Our algorithm returns the smallest area of convex hulls under translation in the same time, and thus it is optimal. For d ≥ 3, we present a deterministic algorithm with running time O (n(d +1)/2) for odd d and O (nd /2 logd n ) for even d. This improves substantially upon the previously best algorithm by a factor at least n(d -1)/2 log n. We also consider the variant that two input polytopes are restricted to remain disjoint, and present a deterministic algorithm with running time O (nd+1) for odd d and O (nd logd -1 n) for even d. This improves substantially upon the previously best algorithm for d > 3 by factor nO (d2) We also study the problem of maximizing the overlap of two convex polytopes under translation in d-dimensional space ℝd for d ≥ 3. We give an -time algorithm, improving substantially upon the previously best algorithm by a factor at least n1-3/d logd +1 n.

The Hilbert metric, introduced by David Hilbert in 1895, is a projective metric defined on a bounded convex domain in a Euclidean space. For a convex polygon with m vertices and n point sites lying inside the polygon in the plane, it is shown that the nearest-point Voronoi diagram in the Hilbert metric has combinatorial complexity of O(mn) [Gezalyan and Mount, SoCG 2023]. In this paper, we show that the farthest-point Voronoi diagram in the Hilbert metric has combinatorial complexity O(m), which is independent of the number of sites. Also, we present an efficient algorithm to compute the farthest-point Voronoi diagram.

We present an algorithm to compute the geodesic $L_1$ farthest-point Voronoi diagram of $m$ point sites in the presence of $n$ rectangular obstacles in the plane. It takes $O(nm+n \log n + m\log m)$ construction time using $O(nm)$ space. This is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query in $O(\log(n+m))$ time.

Given a convex polygon with k vertices and a polygonal domain consisting of polygonal obstacles with n vertices in total in the plane, we study the optimization problem of finding a largest similar copy of the polygon that can be placed in the polygonal domain without intersecting the obstacles. We present an upper bound O(k²n²λ₄(k)) on the number of combinatorial changes occurred to the underlying structure during the rotation of the polygon, together with an O(k²n²λ₄(k)log n)-time deterministic algorithm for the problem. This improves upon the previously best known results by Chew and Kedem [SoCG89, CGTA93] and Sharir and Toledo [SoCG91, CGTA94] on the problem in more than 27 years. Our result also improves the time complexity of the high-clearance motion planning algorithm by Chew and Kedem.

Given a set of sites in a simple polygon, a geodesic Voronoi diagram of the sites partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n -gon, which improve the best known ones for \(m \le n/{\text {polylog}}n\) . Moreover, the algorithms for the geodesic nearest-point and farthest-point Voronoi diagrams are optimal for \(m \le n/{\text {polylog}}n\) . This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.

We study the problem of finding maximum-area rectangles contained in a polygon in the plane. There has been a fair amount of work for this problem when the rectangles have to be axis-aligned or when the polygon is convex. We consider this problem in a simple polygon with $n$ vertices, possibly with holes, and with no restriction on the orientation of the rectangles. We present an algorithm that computes a maximum-area rectangle in $O(n^3\log n)$ time using $O(kn^2)$ space, where $k$ is the number of reflex vertices of $P$. Our algorithm can report all maximum-area rectangles in the same time using $O(n^3)$ space. We also present a simple algorithm that finds a maximum-area rectangle contained in a convex polygon with $n$ vertices in $O(n^3)$ time using $O(n)$ space.

Given a read-only memory for input and a write-only stream for output, an s-workspace algorithm, for a positive integer parameter s, is an algorithm using only O(s) words of workspace in addition to the memory for the input. In this paper, we present an $$O(n^2/s)$$ -time s-workspace algorithm for subdividing a simple n-gon into $$O(\min \{n/s,s\})$$ subpolygons of complexity $$O(\max \{n/s,s\})$$ . As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately by adopting the proposed subdivision: (1) computing the shortest path between two points inside a simple n-gon, (2) computing the shortest-path tree from a point inside a simple n-gon, (3) computing a triangulation of a simple n-gon. In addition, we improve the algorithm for problem (2) further by applying different approaches depending on the size of the workspace.

Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of n disks in the plane. Initially, all disks have radius 0, and they grow at constant, but possibly different, speeds. Whenever two disks touch, the one with the higher index disappears. The goal is to determine the elimination order, i.e., the order in which the disks disappear. We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes (e.g., rectangles), and it works in any fixed dimension. We also describe an alternative algorithm that is based on quadtrees. Its running time is O ( n ( log ⁡ n + min ⁡ { log ⁡ Δ , log ⁡ Φ } ) ) , where Δ is the ratio of the fastest and the slowest growth rate and Φ is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EuroCG 2017]. Finally, we give an Ω ( n log ⁡ n ) lower bound, showing that our quadtree algorithms are almost tight.

We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points s and t in a simple polygon P with no holes, we want to minimize the distance they travel in order to see each other in P. We solve two variants of this problem, one minimizing the longer distance the two persons travel (min-max) and one minimizing the total travel distance (min-sum), optimally in linear time. We also consider a query version of this problem for the min-max variant. We can preprocess a simple n-gon in linear time so that the minimum of the longer distance the two persons travel can be computed in O(log2⁡n) time for any two query positions s,t where the two persons start.

Given a set P of n points in the plane and a multiset W of k weights with k leq n, we assign a weight in W to a point in P to minimize the maximum weighted distance from the weighted center of P to any point in P. In this paper, we give two algorithms which take O(k^2 n^2 log^4 n) time and O(k^5 n log^4 k + kn log^3 n) time, respectively. For a constant k, the second algorithm takes only O(n log^3 n) time, which is near-linear.

We consider the following problem: Preprocess a set S of n axis-parallel boxes in Rd so that given a query with an axis-parallel box in Rd, the pairs of boxes of S whose intersection intersects the query box can be reported efficiently. For the case that d=2, we present a data structure of size O(nlog⁡n) supporting O(log⁡n+k) query time, where k is the size of the output. This improves the previously best known result by de Berg et al. which requires O(log⁡n+klog⁡n) query time using O(nlog⁡n) space. There has been no result known for this problem for higher dimensions, except that for d=3, the best known data structure supports O(nlog2⁡n+klog2⁡n) query time using O(nnlog⁡n) space. For a fixed dimension d>2, we present a data structure supporting O(n1−δlogd−1⁡n+klogd−1⁡n) query time for any constant 0<δ<1. The size of the data structure is O(nδd−2δ+1log⁡n).

This paper proposes a simple nearest neighbor search algorithm, which provides the exact solution in terms of the Euclidean distance efficiently. Especially, we present an interesting approach to improve the speed of nearest neighbor search by proper translations of data and query although the task is inherently invariant to the Euclidean transformations. The proposed algorithm aims to eliminate nearest neighbor candidates effectively using their distance lower bounds in nonlinear embedded spaces, and further improves the lower bounds by transforming data and query through product quantized translations. Although our framework is composed of simple operations only, it achieves the state-of-the-art performance compared to existing nearest neighbor search techniques, which is illustrated quantitatively using various large-scale benchmark datasets in different sizes and dimensions.

We study the approximate range searching for three variants of the clustering problem with a set $P$ of $n$ points in $d$-dimensional Euclidean space and axis-parallel rectangular range queries: the $k$-median, $k$-means, and $k$-center range-clustering query problems. We present data structures and query algorithms that compute $(1+\varepsilon)$-approximations to the optimal clusterings of $P\cap Q$ efficiently for a query consisting of an orthogonal range $Q$, an integer $k$, and a value $\varepsilon>0$.

We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. Precisely, the amortized update time is O(sqrt{n}log n(log log n)^{3/2}) and the query time is O(log n(log log n)^2), where n is the number of edges in the subdivision. This answers a question posed by Snoeyink in the Handbook of Computational Geometry. When only deletions of edges are allowed, the update time and query time are just O(alpha(n)) and O(log n), respectively.

We consider the geodesic convex hulls of points in a simple polygonal region in the presence of non-crossing line segments (barriers) that subdivide the region into simply connected faces. We present an algorithm together with data structures for maintaining the geodesic convex hull of points in each face in a sublinear update time under the fully-dynamic setting where both input points and barriers change by insertions and deletions. The algorithm processes a mixed update sequence of insertions and deletions of points and barriers. Each update takes O(n^2/3 log^2 n) time with high probability, where n is the total number of the points and barriers at the moment. Our data structures support basic queries on the geodesic convex hull, each of which takes O(polylog n) time. In addition, we present an algorithm together with data structures for geodesic triangle counting queries under the fully-dynamic setting. With high probability, each update takes O(n^2/3 log n) time, and each query takes O(n^2/3 log n) time.

Motivated by map labeling, we study the problem in which we are given a collection of n disks in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the higher index disappears. This problem was introduced by Funke, Krumpe, and Storandt[IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension. Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an \Omega(n\log n) lower bound on the problem, showing that our quadtree algorithms are almost tight.

Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon.

We consider the problem of finding a shortcut connecting two vertices of a graph that minimizes the diameter of the resulting graph. We present an O(n^2 log^3 n)-time algorithm using linear space for the case that the input graph is a tree consisting of n vertices. Additionally, we present an O(n^2 log^3 n)-time algorithm using linear space for a continuous version of this problem.

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an O(n log n)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.

We propose an efficient algorithm to find the exact nearest neighbor based on the Euclidean distance for large-scale computer vision problems. We embed data points nonlinearly onto a low-dimensional space by simple computations and prove that the distance between two points in the embedded space is bounded by the distance in the original space. Instead of computing the distances in the high-dimensional original space to find the nearest neighbor, a lot of candidates are to be rejected based on the distances in the low-dimensional embedded space; due to this property, our algorithm is well-suited for high-dimensional and large-scale problems. We also show that our algorithm is improved further by partitioning input vectors recursively. Contrary to most of existing fast nearest neighbor search algorithms, our technique reports the exact nearest neighbor - not an approximate one - and requires a very simple preprocessing with no sophisticated data structures. We provide the theoretical analysis of our algorithm and evaluate its performance in synthetic and real data.

We present an algorithm to compute an approximate overlap of two convex polytopes P_1 and P_2 in R^3 under rigid motion. Given any epsilon in (0,1/2], our algorithm runs in O(epsilon^{-3}n log^{3.5}n) time with probability 1 - n^{-O(1)} and returns a (1-epsilon)-approximate maximum overlap, provided that the maximum overlap is at least lambda max(|P_1|,|P_2|) for some given constant lambda in (0,1].

Given a set V of n vectors in d-dimensional space, we provide an efficient method for computing quality upper and lower bounds of the Euclidean distances between a pair of the vectors in V . For this purpose, we define a distance measure, called the MS-distance, by using the mean and the standard deviation values of vectors in V . Once we compute the mean and the standard deviation values of vectors in V in O(dn) time, the MS-distance between them provides upper and lower bounds of Euclidean distance between a pair of vectors in V in constant time. Furthermore, these bounds can be refined further such that they converge monotonically to the exact Euclidean distance within d refinement steps. We also provide an analysis on a random sequence of refinement steps which can justify why MS-distance should be refined to provide very tight bounds in a few steps of a typical sequence. The MS-distance can be used to various problems where the Euclidean distance is used to measure the proximity or similarity between objects. We provide experimental results on the nearest and the farthest neighbor searches.

The aperture angle α(x, Q) of a point x∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q ⊂ C is the minimum aperture angle of any x ∈ C ࢨ Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q ⊂ C with aperture angle approximation error (1 - 2/k+1)π. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/k+1 sin π/k+1.

Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 - ε times the maximum possible overlap. Our algorithm uses O(1/ε) extreme point and line intersection queries on P and Q, plus O((1/ε2) log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total, the total running time is O((1/ε) log n + (1/ε2) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.

Let B be a point robot moving in the plane, whose path is constrained to forward motions with a curvature at most 1, and let P be a convex polygon with n vertices.Given a starting configuration (a location and a direction of travel) for B inside P, we characterize the region of all points of P that can be reached by B, and show that it has linear complexity.

In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the cast consists of two parts and address the following problems. (1) Given a cast for an object and a direction , can the cast be partitioned into two parts such that the parts can be removed in directions and - , respectively, without colliding with the object or the other cast part? (2) How can one find a direction such that the above cast partitioning can be done? We give necessary and sufficient conditions for both problems, as well as algorithms to decide them for polyhedral objects. We also give some evidence that the case where the cast parts need not be removed in opposite directions is considerably harder.