In this article, we consider the problems of finding in d + 1 dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of d -dimensional unit-radius balls can be packed under translations. The computational problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm for each of these containers based on a reduction to finding a shortest Hamiltonian path in a weighted graph, which in turn models the problem of stabbing the centers of the input balls while keeping them disjoint. We also show that for n such balls, a container of volume O ( n d − 1 d ) is always sufficient and sometimes necessary. As a byproduct, this implies that for d ⩾ 2 there is no finite size ( d + 1 ) -dimensional convex body into which all d -dimensional unit-radius balls can be packed simultaneously.

Let $P$ be a set of at most $n$ points and let $R$ be a set of at most $n$ geometric ranges, such as for example disks or rectangles, where each $p \in P$ has an associated supply $s_{p} > 0$, and each $r \in R$ has an associated demand $d_{r} > 0$. A (many-to-many) matching is a set $\mathcal{A}$ of ordered triples $(p,r,a_{pr}) \in P \times R \times \mathbb{R}_{>0}$ such that $p \in r$ and the $a_{pr}$'s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing $\sum_{(p,r,a_{pr}) \in \mathcal{A}} a_{pr}$. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of $n$ red points $P$ and a set of $n$ blue points $Q$ that minimizes the length of the longest edge. For the $L_\infty$-metric, we can do this in time $O(n^{1+\varepsilon})$ in any fixed dimension, for the $L_2$-metric in the plane in time $O(n^{4/3 + \varepsilon})$, for any $\varepsilon > 0$.

We prove a generalization of Pál's 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360° inside Q. We also prove a lower bound of Omega(m n^{2}) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.

Let C be the unit circle in R^2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k^(2/3)) for any k.

We show that the union of n translates of a convex body in $$\mathbb {R}^3$$ can have $$\varTheta (n^3)$$ holes in the worst case, where a hole in a set X is a connected component of $$\mathbb {R}^3 \setminus X$$ . This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.

The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively.

Given four congruent balls A,B,C,D in Rδ that have disjoint interior and admit a line that intersects them in the order ABCD, we show that the distance between the centers of consecutive balls is smaller than the distance between the centers of A and D. This allows us to give a new short proof that n interior-disjoint congruent balls admit at most three geometric permutations, two if n⩾7. We also make a conjecture that would imply that n⩾4 such balls admit at most two geometric permutations, and show that if the conjecture is false, then there is a counter-example that is algebraically highly degenerate.

Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.

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 S be an ordered set of disjoint unit spheres in R3 We show that if every subset of at most six spheres from S admits a line transversal respecting the ordering, then the entire family has a line transversal. Without the order condition, we show that the existence of a line transversal for every subset of at most 11 spheres from S implies the existence of a line transversal forS.

(MATH) In the one-round Voronoi game, the first player chooses an n-point set $\PFRST$ in a square $Q$, and then the second player places another n-point set $\PSCND$ into $Q$. The payoff for the second player is the fraction of the area of $Q$ occupied by the regions of the points of $\PSCND$ in the Voronoi diagram of $\PFRST\cup\PSCND$. We give a strategy for the second player that always guarantees him a payoff of at least $\frac12+\alpha$, for a constant $\alpha>0$ independent of n. This contrasts with the one-dimensional situation, with $Q=[0,1]$, where the first player can always win more than 1/2.

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.

We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of m barriers.We obtain the following results:if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost O(min(m2, mfi)); if the barriers are disjoint line segments, then there is always a spanning tree of cost O(m); if the barriers are disjoint fat objects, discs for example, then there is always a spanning tree of cost O(n + m).All our bounds are worst-case optimal.

A new hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have maximum degree three. Using this hierarchy, circular ray shooting queries in a simple polygon can be answered in O(log* n) query time and O(nlogn) space. If the radius of the circle is fixed, the query time can be improved to O(logn) and the space to O(n). The decomposition is also applied to three other circular arc query problems: shortest directed arc, arc bending, and arc pushing. Using these queries, the largest empty lune determined by two query points in a simple polygon can be computed in O(log3 n) time, while the circular visibility region of a query point in a simple polygon can be reported in time O(m log3 n), where m is the output size.

We give simple randomized incremental algorithms for computing the Amk-level in an arrangement of n lines in the plane or in an arrangement of n planes in $\Reals^3$. The expected running time of our algorithms is $O(nk+n\alpha(n)\log n)$ for the planarcase and O(nk 2 + n log 3 n) for the three-dimensional case. Both bounds are optimal unless k is very small. The algorithm generalizes to computing the Amk-level in an arrangement of discs or x-monotone Jordan curves in the plane. Our approach can also compute the k-level; this yields a randomized algorithm for computing the order-k Voronoi diagram of n points in the plane in expected time O(k(n-k)log n + n log 3 n).

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized $O(n \log n)$ expected time algorithm for computing $\sqrt{n}$ cells in an arrangement of n lines.

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.

Let X be a collection of n algebraic surface patches of constant maximum degree in IR3.We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement A(Z) is 0(n2+E ), for my E > CI, where the constant of proportionality de pends on E and on the maximum degree of the surfaces and of their boundaries.As an application, we obt~"n a near-quadratic motion planning algorithm for general systems with three degrees of freedom.

Voronoi diagrams of curved objects can show certa"n phenomena that are often considered artifacts:

A familiar task in inclu.striala~)l>lications is gras~jing

No abstract available.

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region Rα(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of Rα(S) is O(nα5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

We give a simple lazy randomized incremental algorithm to compute ≤k-levels in arrangements of x-monotone Jordan curves in the plane, and in arrangements of planes in three-dimensional space. If each pair of curves intersects in at most s points, the expected running time of the algorithm is O(k2λs(n/k)+min(λs(n)log2n,k2λs(n/k)logn)). For the three-dimensional case the expected running time is O(nk2+min(nlog3n,nk2logn)). The algorithm also works for computing the ≤k-level in a set of discs, with an expected running time of O(nk+min(nlog2n,nklogn)). Furthermore, we give a simple algorithm for computing the order-k Voronoi diagram of a set of n points in the plane that runs in expected time O(k(n−k)logn+nlog3n).

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(nlogn) expected time algorithm for computing √n cells in an arrangement of n lines.

We introduce a new type of randomized incremental algorithms.Con trary to standard randomized incremental al-

A depth order on a set of line segments in 3-space is an order such that line segment a comes before line segment $a'$ in the order when a lies below $a'$ or, in other words, when there is a vertical ray that first intersects $a'$ and then intersects a. Efficient algorithms for the computation and verification of depth orders of sets of n line segments in 3-space are presented. The algorithms run in time $O(n^{{4 / 3} + \varepsilon } )$, for any fixed $\varepsilon > 0$. If all line segments are axis-parallel or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in $O(n\log ^3 n)$, for any fixed $\varepsilon > 0$ time and the verification takes $O(n\log ^2 n)$ time. The algorithms can be generalized to handle triangles and other polygons instead of line segments. They are based on a general framework for computing and verifying linear orders extending implicitly defined binary relations.

Let B be a set of n arbitrary (possibly intersecting) convex obstacles in Rd.It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting of 0(nId-l)ld/2+1~) segments.The bound cannot be improved below Q(nd); thus in R3, the answer is between n3 and n4.For disjoint obstacles, a ~(n) bound is proved.By a well-known reduction, thegeneralca.seresult also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles.In the planar case, asymptotically tight bounds and efficient algorithms are given.1

We give a deterministic algorithm for computing the diameter of an n point set in ti~ree dimensions with O(n log' n) running time, c a constant.

A depth order on a set of objects is an order such that object a comes before object a′ in the order when a′ lies behind a′, or, in other words, when a is (partially) hidden by a′ by a′. We present efficient algorithms for the computation and verification of depth orders of sets of n rods in 3–space. Our algorithms run in time O(n4/3+ε), for any fixed ε > 0). If all rods are axis-parallel, or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in O(n log2 n) time. The algorithms can be generalized to handle triangles and other polygons instead of rods. They are based on a general framework for computing and verifying linear extensions of implicitly defined binary relations.

Article Free Access Share on Linear optimization queries Authors: Jiří Matoušek View Profile , Otfried Schwarzkopf View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992 Pages 16–25https://doi.org/10.1145/142675.142683Online:01 July 1992Publication History 42citation441DownloadsMetricsTotal Citations42Total Downloads441Last 12 Months23Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let H be a set of n halfspaces in Ed (where the dimension d ≥ 4 is fixed), and P(H) the convex polytope defined as their intersection. We show that P(H) can be preprocessed in time and space O(n[d/2]/(log n)[d/2]-ε) (for any fixed ε > 0) so that ray shooting queries with rays starting in P(H) can be answered in time O(log n). This improves previous bounds by obtaining optimal query time and by improving the product Q(n)S(n)1/[d/2] (Q(n) and S(n) denoting query time and storage of a data structure for this problem) to O(n(log n)ε) for an arbitrarily small ε > 0. By a well known lifting transformation, the results imply the same bounds for nearest (or furthest) neighbor queries in space of one dimension lower, which is an improvement in itself. We furthermore show that a structure for the ray shooting problem can be dynamically maintained under a sequence of random insertions, using the history of the maintenance process for the polytope as a point location data structure. The expected update time is O(m[d/2]-1(log m)O(1)), the query time for ray shooting queries is O(log2 m) with high probability, where m is the current number of points.

Article Free Access Share on A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams Authors: Franz Aurenhammer Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, Germany Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, GermanyView Profile , Otfried Schwarzkopf Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, Germany Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W1000 Berlin 33, GermanyView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 142–151https://doi.org/10.1145/109648.109664Published:01 June 1991Publication History 16citation832DownloadsMetricsTotal Citations16Total Downloads832Last 12 Months55Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of dynamically maintaining geometric structures is considered. A technique is proposed that uses randomized incremental algorithms which are augmented to allow deletions of objects. A model for distributions on the possible input sequences of insertions and deletions is developed and analyzed using R. Seidel's backwards analysis. It is further shown how to apply this to maintain Voronoi diagrams, convex hulls, and planar subdivisions. A strikingly simple algorithm for the maintenance of convex hulls in any dimension is given. The expected running time is determined.>

We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in @@@@d in time 𝒪(Τd(N, N) logd N), where Τd(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in @@@@d. If Τd(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to 𝒪(Τd(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time 𝒪((nm log n log m)2/3 + m log2 n + n log2 m) in @@@@3, which yields an 𝒪(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in @@@@3.