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.

We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (tj) and radii (rj) that cover a given set of demand points Y∈R2 at the smallest possible cost. We consider cost functions of the form Εjf(rj), where f(r)=rα is the cost of transmission to radius r. Special cases arise for α=1 (sum of radii) and α=2 (total area); power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers tj, which may be constrained to belong to a given discrete set or to lie on a line, etc.We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y∈R2; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in R2 and any fixed α>1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.

We consider the problem of reconfiguring a linkage of rigid straight segments from a given start to a given target position with a continuous nonintersecting motion. The problem is nontrivial even for trees in two dimensions since it is known that not all configurations can be reconfigured to a straight position. We show that deciding reconfigurability for trees in two dimensions and for chains in three dimensions is PSPACE-complete.

Given a polygonal curve and a geometric graph, we describe an efficient algorithm to find a path in the graph which is most similar to the curve, using the well-known Fréchet distance for curves.

We present an algorithm for solving the nearest neighbor problem with respect to $L_{\infty}$-distance. It requires no preprocessing and storage only for the point set $P$. Its average runtime assuming that the set $P$ of $n$ points is drawn randomly from the unit cube $[0,1]^{d}$ under uniform distribution is essentially $\Theta (nd/ln\; n)$ thereby improving the brute-force method by a factor of $\Theta (1/ln\; n)$. Several generalizations of the method are also presented, in particular to other “well-behaved” probability distributions and to the important problem of finding the $k$ nearest neighbors to a query point.

Article Point-sets with few k-sets Share on Authors: Helmut Alt Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, Germany Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, GermanyView Profile , Stefan Felsner Institut für Informatik, Freie Universität Berlin, Takustr. 9 14195 Berlin, Germany Institut für Informatik, Freie Universität Berlin, Takustr. 9 14195 Berlin, GermanyView Profile , Ferran Hurtado Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, España Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, EspañaView Profile , Marc Noy Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, España Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, EspañaView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 200–205https://doi.org/10.1145/276884.276907Published:07 June 1998 0citation149DownloadsMetricsTotal Citations0Total Downloads149Last 12 Months0Last 6 weeks0 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 SiteGet Access

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

For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the minimum Hausdorff distance which can be achieved in this way. The algorithm just matches the so-called Steiner points of the two sets.

Article Measuring the resemblance of polygonal curves Share on Authors: Helmut Alt View Profile , Michael Godau View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992 Pages 102–109https://doi.org/10.1145/142675.142699Online:01 July 1992Publication History 41citation939DownloadsMetricsTotal Citations41Total Downloads939Last 12 Months52Last 6 weeks4 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 SiteGet Access

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time Ω(n2) where n is the number of obstacle corners. We introduce the tightness of a motion planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with running time ο((a/b · 1/ε crit + 1)n(log n)2), where a ≥ b are the lengths of the sides of a rectangle and εcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary of n bow-ties (c.f. Figure 1.1) is Ο(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.

For two given simple polygons P, Q the problem is to determine a rigid motion I of Q giving the best possible match between P and Q, i.e. minimizing the Hausdorff-distance between P and I(Q). Faster algorithms as the one for the general problem are obtained for special cases, namely that I is restricted to translations or even to translations only in one specified direction. It turns out that determining pseudo-optimal solutions, i.e. ones that differ from the optimum by just a constant factor can be done much more ejjiciently than determining op-timal solutions. In the most general case the algorithm for the pseudo-optimal solution is based on the quite sur-prising fact that for the optimal possible match between P and an image I(Q) of Q the distance between the cen-troids of the edges of the convex hulls of P and I(Q] is a constant multiple of the Hausdorff-distance between P and I(Q). It is also shown that the Hausdorff-distance between two simple polygons can be determined in time O(n log n], where n is the total number of vertices.

Methods are presented for finding reductions between the computations of certain arithmetic functions that preserve asymptotic Boolean complexities (circuit depth or size). They can be used to show, for example, that all nonlinear algebraic functions are as difficult as integer multiplication with respect to circuit size. As a consequence, any lower or upper bound (e.g., O ( n log n log log n )) for one of them applies to the whole class. It is also shown that, with respect to depth and size simultaneously, multiplication is reducible to any nonlinear and division to any nonpolynomial algebraic function.

No abstract available.

We prove a Θ(log log n ) (i.e. matching upper and lower) bound on the complexity of the Union-Split-Find problem, a variant of the Union-Find problem. Our lower bound holds for all pointer machine algorithms and does not require the separation assumption used in the lower bound arguments of Tarjan [T79] and Blum [B86]. We complement this with a Θ(log n ) bound for the Split-Find problem under the separation assumption. This shows that the separation assumption can imply an exponential loss in efficiency.

We describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM’s shared memory is polynomial in n, each PRAM step is simulated by $O(\log n)$ MPC steps or by $O((\log n)^2 )$ steps of the bounded-degree network.This improves upon a previous result by Upfal and Wigderson. We also prove an $\Omega ({{(\log n)^2 } / {\log \log n}})$ lower bound on the number of steps needed to simulate one PRAM step on a bounded-degree network under the assumption that the communication in the network is point to point. As an important part of the simulation of PRAMs on MPCs, we use a new technique for dynamically averaging out a given work load among a set of processors operating in parallel.

A “semisorted table” is a one-dimensional array containing n data, which are not necessarily sorted, but can appear in p different permutations of the ascending order. We consider the problem of searching in such a table without knowing, in which one of the p permutations the data are stored (SST). It is shown that any deterministic search algorithm for SST needs at least $\sqrt[n]{p}$ comparisons in the worst case. This lower bound is generalized to average case performance even for nondeterministic algorithms. Some examples are given where the lower bound is tight.

It is shown that floating point (or integer) multiplication can be reduced to the evalution of a very large class of functions including most of the nontrivial functions used in practice. That means that whenever any such function can be evaluated by boolean circuits of size S(n), then multiplication can be done with circuits of size O(S(n)). as well.