
A PTAS for Minimum Clique Partition in Unit Disk Graphs
Imran Pirwani, Mohammad SalavatipourWe consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NPhard and various constant factor approximations are known, with the current best ratio of 3. Our main result is a polynomial time approximation scheme (PTAS) for this problem on UDG. In fact, we present a weaklyrobust algorithm that given a graph G (not necessarily UDG) with edgelengths, it either (i) computes a clique partition or (ii) gives a certificate that the graph is not a UDG; for the case (i) that it computes a clique partition, we show that it is guaranteed to be within (1 + ε) ratio of the optimum if the input is UDG; however if the input is not a UDG it either computes a clique partition as in case (i) with no guarantee on the quality of the clique partition or detects that it is not a UDG. Noting that recognition of UDG’s is NPhard even if we are given edge lengths, our PTAS is a weaklyrobust algorithm. Our main technical contribution involves showing the property of separability of an optimal clique partition: that there exists an optimal clique partition where the convex hulls of the cliques are pairwise nonoverlapping. Our algorithm can be transformed into an O(log*n/ε^O(1)) time distributed polynomialtime approximation scheme (PTAS). Finally, we consider a weighted version of the clique partition problem on vertex weighted UDGs given given in the standard form (e.g. adjacency matrix); the weight of a clique is the weight of a heaviest vertex in it, and the weight of a clique partition is the sum of the weights of the cliques in it. This formulation generalizes the classical clique partition problem. We note some key distinctions between the weighted and the unweighted versions, where ideas developed for the unweighted case do not help. Yet, surprisingly, we show that the problem admits a (2 + ε)approximation algorithm for the weighted version of the problem even when the graph is expressed in standard form. This improves on the best known algorithm which constructs an 8approximation for the unweighted case for UDGs expressed in standard form.

A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing.
Aparna Das, Claire MathieuIn the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasipolynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.

On the Exact Space Complexity of Sketching and Streaming Small Norms
Daniel M. Kane, Jelani Nelson, David P. WoodruffWe settle the 1pass space complexity of (1+eps)approximating the Lp norm, for real p with 1 <= p <= 2, of a lengthn vector updated in a lengthm stream with updates to its coordinates. We assume the updates are integers in the range [M, M]. In particular, we show the space required is Theta(eps^{2}*log(mM) + loglog(n)) bits. Our result also holds for 0 < p < 1; although Lp is not a norm in this case, it remains a welldefined function. Our upper bound improves upon previous algorithms of [Indyk, JACM '06] and [Li, SODA '08]. This improvement comes from showing an improved derandomization of the Lp sketch of Indyk by using kwise independence for small k, as opposed to using the heavy hammer of a generic pseudorandom generator against spacebounded computation such as Nisan's PRG. Our lower bound improves upon previous work of [AlonMatiasSzegedy, JCSS '99] and [Woodruff, SODA '04], and is based on showing a direct sum property for the 1way communication of the gapHamming problem.

Hardness Results of Homology Localization
Chao Chen, Daniel FreedmanWe address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We focus on the volume measure, that is, the 1norm of a cycle. Two main results are presented. First, we prove the problem is NPhard to approximate within any constant factor. Second, we prove that for homology of 2dimension or higher, the problem is NPhard to approximate even when the Betti number is $O(1)$. A side effect is the inapproximability of the problem of computing the nonbounding cycle with the smallest volume, and computing cycles representing a homology basis with the minimal total volume. We also discuss other geometric measures (diameter and radius) and show their disadvantages in homology localization.

Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
Petr Hlineny, Markus ChimaniWe provide an $O(n\log n)$ time constant factor approximation algorithm for the crossing number of a graph of bounded maximum degree which is ``densely enough'' embeddable on any fixed orientable surface. Our approach combines some known tools with a powerful new lower bound on the crossing number of an embedded graph. This result extends previous results that gave such approximations in particular cases of projective, toroidal or apex graphs; it is a qualitative improvement over previously published algorithms that constructed lowcrossingnumber drawings of embeddable graphs without giving any approximation guarantees. No constant factor approximation algorithms for the crossing number problem over comparably rich classes of graphs are known to date.

Data Structures for Range Minimum Queries in Multidimensional Arrays
Hao Yuan, Mikhail J. AtallahGiven a ddimensional array A with N entries, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray of A. The 1D RMQ problem has been studied intensively because of its relevance to the Nearest Common Ancestor problem and its important use in stringology. If constanttime query answering is required, linear time and space preprocessing algorithms were known for the 1D case, but not for the higher dimensional cases. In this paper, we give the first lineartime preprocessing algorithm for arrays with fixed dimension, such that any range minimum query can be answered in constant time. This improves the preprocessing time over all previous work under the same model, i.e., RAM with logarithmic word size.

On the Optimality of Spiral Search
Elmar LangetepeSearching for a point in the plane is a wellknown search game problem introduced in the early eigthies. The best known search strategy is given by a spiral and achieves a competitive ratio of 17.289.... It was shown by Gal \cite{gsg80} that this strategy is the best strategy among all \emph{monotone} and \emph{periodic} strategies. Since then it was unknown whether the given strategy is optimal in general. This paper settles this old open fundamental search problem and shows that spiral search is indeed optimal. The given problem can be considered as the continous version of the wellknown $m$ray search problem and also appears in several nongeometric applications and modifications. Therefore the optimality of spiral search is an important questions considered by many researchers in the last decades. We answer the logarithmic spiral conjecture for the given problem. The lower bound construction might be helpful for similar settings, it also simplifies existing proofs on classical $m$ray search.

The focus of attention problem
Dries Goossens, Sergey Polyakovskiy, Frits Spieksma, Gerhard WoegingerMotivated by applications in the area of sensor networks, Isler, Khanna, Spletzer and Taylor (2005) discuss an algorithmic problem where 2n cameras have to be assigned in disjoint pairs to n targets. The cameras are located on a straight line, whereas the targets are somewhere in the plane. They assume that the 2n cameras are positioned on the xaxis, in the 2n points with coordinates (x(i), 0) with 1 <= i <= n. They discuss an error measure motivated by stereo reconstruction that mainly depends on the ycoordinates y(1),..., y(n) of the n targets: If the ith and the jth camera together are assigned to the kth target, then the corresponding incurred error cost is c(ijk) = y(k)/(x(i)x(j)). The objective is to find an assignment of camera pairs to targets such that the sum of all error costs c(ijk) is minimized.
We investigate a generalization of this cost structure that is based on a real parameter p. An instance of problem pFOA is specified by 2n real numbers x(1),...,x(2n) and by n real numbers y(1),...,y(n). The corresponding costcoefficient for matching x(i) and x(j) with y(k) is c(ijk) = y(k)/(x_ix_j^p). The goal is to find an assignment that minimizes the sum of all costs. We provide a complete complexity classification of problem pFOA:
 For every real p with 1 <= p <= 0, problem pFOA is polynomially solvable.
 For every real p with p < 1 or p > 0, problem pFOA is strongly NPhard.
 Even the special case with equidistant cameras is strongly NPhard. This settles a question left open in Isler et al. (2005).
 For every real p, problem pFOA possesses a PTAS.

A localitysensitive hash for real vectors
Tyler NeylonWe present a simple and practical algorithm for the $c$approximate near neighbor problem ($c$NN): given $n$ points $P\subset\R^d$ and radius $R$, build a data structure which, given $q\in\R^d$, can with probability $1\delta$ return a point $p\in P$ with $\mathsf{dist}(p,q)\le cR$ if there is any $p^*\in P$ with $\mathsf{dist}(p^*,q)\le R$. For $c=d+1$, our algorithm deterministically ($\delta=0$) preprocesses in time $O(nd\log d)$, space $O(dn)$, and answers queries in expected time $O(d^2)$; this is the first known algorithm to deterministically guarantee an $O(d)$NN solution in constant time with respect to $n$ for all $\ell_p$ metrics. A probabilistic version empirically achieves useful $c$ values ($c < 2$) where $c$ appears to grow minimally as $d\to\infty$. A query time of $O(d\log d)$ is available, providing slightly less accuracy. These techniques can also be used to approximately find (pointers between) all pairs $x,y\in P$ with $\mathsf{dist}(x,y) \le R$ in time $O(nd\log d)$.
The key to the algorithm is a localitysensitive hash: a mapping $h:\R^d\to U$ with the property that $h(x) = h(y)$ is much more likely for nearby $x,y$. We introduce a somewhat regular simplex which tessellates $\R^d$, and efficiently hash each point in any simplex of this tessellation to all $d+1$ corners; any points in neighboring cells will be hashed to a shared corner and noticed as nearby points. This method is completely independent of dimension reduction, so that additional space and time savings are available by first reducing all input vectors.

The forest hiding problem
Adrian Dumitrescu, Minghui JiangLet Ω be a disk of radius $R$ in the plane. A set $F$ of closed unit disks contained in Ω forms a maximal packing if the unit disks are pairwise disjoint and the set is maximal: i.e., it is not possible to add another disk to $F$ while maintaining the packing property. A point $p$ is hidden within the ``forest'' defined by $F$ if any ray with apex $p$ intersects some disk of $F$: that is, a person standing at $p$ can hide without being seen from outside the forest. We show that if the radius $R$ of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph~Mitchell. We also present an $O(n^{5/2} \log n)$time algorithm that, given a forest with $n$ (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest.

How to meet asynchronously (almost) everywhere
Jurek Czyzowicz, Arnaud Labourel, Andrzej PelcTwo mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerfull adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with pathconnected interior. While our algorithms work in a very general setting  agents can, indeed, meet almost everywhere  we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other.

Convergence, Stability, and Discrete Approximation of Laplace Spectra
Tamal K. Dey, Pawas Ranjan, Yusu WangSpectral methods have been widely used in a broad range of application fields. One important object involved in such methods is the LaplaceBeltrami operator of a manifold. Indeed, a variety of work in graphics and geometric optimization uses the eigenstructures of the Laplace operator, and applications include mesh smoothing, compression, editing, shape segmentation, matching, and parametrization, among others. While the Laplace operator is defined (mathematically) for a smooth domain, in these applications, the underlying manifold is often approximated by a discrete mesh, and the spectral structure of the manifold Laplacian is estimated from some discrete Laplace operator constructed from this mesh. In this paper, we study the important question of how well the spectrum computed from the discrete mesh approximates the true spectrum of the manifold Laplacian. We exploit a recent result on mesh Laplacian and provide the first convergence result to relate the spectrum constructed from a mesh with the true spectrum. We also study how stable these eigenstructures and their discrete approximations are when the underlying manifold is perturbed, and provide explicit bounds for the Laplacian spectra of two ``close'' manifolds, as well as a convergence result for their discrete approximations. Finally, we present various experimental results to demonstrate that these discrete spectra are both accurate and robust in practice.

Generating a ddimensional linear subspace efficiently
Rapahael YusterWe present an algorithm for computing a $d$dimensional subspace of the row space of a matrix. For an $n \times n$ matrix $A$ with $m$ nonzero entries and with $rank(A) \ge d$ the algorithm generates a $d \times n$ matrix with full row rank and which is a subspace of $Rows(A)$. If $rank(A) < d$ the algorithm generates a $rank(A) \times n$ rowequivalent matrix. The running time of the algorithm is
O( min{ n^{22/ω} m^{1/ω} d^{ω2+1/ω}, n^2 d^{ω2} } ) where ω < 2.376 is the matrix multiplication exponent. An immediate corollary of the algorithm is the construction of a rowreduced equivalent matrix of $A$, and hence the computation of $rank(A)$, in time $O( min {n^{22/ω} m^{1/ω} rank(A)^{ω2+1/ω}, n^2 rank(A)^{ω2} } )$. We note that the running time is subquadratic if d < (n^2/m)^{0.528}. 
Coresets and Sketches for High Dimensional Subspace Approximation Problems
Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. WoodruffGiven a point set $P$ in $\REAL^d$, an $F_q(\ell_p)$subspace approximation problem asks for a subspace that minimizes the sum of $q$th powers of $\ell_p$distances to this subspace. In this paper we develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set $P$ with respect to a subspace approximation problem. Our results are:
 A dimensionality reduction method that can be applied to $F_q(\ell_p)$clustering and shape fitting problems \cite{DDHKM09, Har06c}.
 The first strong coreset for $F_1(\ell_2)$subspace approximation in high dimensional spaces, i.e. of size polynomial in the dimension of the space.
 A $(1+\epsilon)$approximation algorithm for the $j$dimensional $F_1(\ell_2)$subspace approximation problem with running time $O(nd (j/\eps)^{O(1)} + (n+d) 2^{O(j/\epsilon)^{O(1)}})$.
 A streaming algorithm that maintains a coreset for the $F_1(\ell_2)$subspace approximation problem and uses $\tilde{O}(d(\frac{j2^{ O(\sqrt{\log n})}}{\epsilon^2})^{\poly(j)})$ space, where the space gives the number of memory cells used.
 Several streaming algorithm with bounded precision in the turnstile model. We significantly extend the results of \cite{CW09} for approximate linear regression, distance to subspace approximation, and best rank$j$ approximation, to error measures other than the Frobenius norm, obtaining $1$pass sublinear, nearoptimal space complexity for these problems. Our time is always polynomial for constant $j/\eps$, even for the time to extract a $(1+\eps)$approximation to the best rank$j$ subspace from the sketch.

How far can you reach?
Ciprian Borcea, Ileana StreinuRobot Arm Reachability, the problem of computing the extremal configurations of a 3D revolutejointed manipulator, is a long standing open problem in Robotics. In this paper we completely solve it for orthogonal polygonal chains, which appear as a special case of a larger family, fully characterized here by a technical condition. Until now, in spite of the practical importance of the problem, only numerical optimization heuristics were available. These were not even guaranteed to produce the optimum; in fact, the problem was not even known to be computationally solvable, and in practice, the numerical heuristics were applicable only to small problem sizes.
We present surprisingly elementary and efficient (mostly linear time) algorithms for four fundamental problems: (1) finding the minimum and the maximum reach value, (2) finding an extremal configuration (or enumerating all of them), (3) folding a given chain to a given extremal position, and (4) folding a chain in a way that changes the endpoint distance function monotonically. Our theoretical results reduce the first problem to finding a shortest path between two vertices in an associated simple triangulated polygon, and the last problem to a simple version of the planar Carpenter's Rule Problem.

Sharp Dichotomies for Regret Minimization in Metric Spaces
Robert Kleinberg, Aleksandrs SlivkinsThe Lipschitz multiarmed bandit (MAB) problem generalizes the classical multiarmed bandit problem by assuming one is given side information consisting of a priori upper bounds on the difference in expected payoff between certain pairs of strategies. Classical results of Lai and Robbins and Auer et al imply a logarithmic regret bound for the Lipschitz MAB problem on finite metric spaces. Recent results on continuumarmed bandit problems and their generalizations imply lower bounds of $\sqrt{t}$, or stronger, for many infinite metric spaces such as the unit interval. Is this dichotomy universal? We prove that the answer is yes: for every metric space, the optimal regret of a Lipschitz MAB algorithm is either bounded above by any $f\in \omega(\log t)$, or bounded below by any $g\in o(\sqrt{t})$. Perhaps surprisingly, this dichotomy does not coincide with the distinction between finite and infinite metric spaces; instead it depends on whether the completion of the metric space is compact and countable. Our proof connects upper and lower bound techniques in online learning with classical topological notions such as perfect sets and the CantorBendixson theorem.
We also consider the "fullfeedback" (a.k.a., "bestexpert") version of Lipschitz MAB problem, termed the "Lipschitz experts problem", and show that this problem exhibits a similar dichotomy. We proceed to give nearly matching upper and lower bounds on regret in the Lipschitz experts problem on uncountable metric spaces. These bounds are of the form $\tilde{\Theta}(t^\gamma)$, where the exponent $\gamma\in [\tfrac12, 1]$ depends on the metric space. To characterize this dependence, we introduce a novel dimensionality notion tailored to the experts problem. Finally, we show that both Lipschitz bandits and Lipschitz experts problems become completely intractable (in the sense that no algorithm has regret $o(t)$) if and only if the completion of the metric space is noncompact.

The Complexity of Guarding Terrains
James King, Erik KrohnA set G of points on a 1.5dimensional terrain, also known as an xmonotone polygonal chain, is said to guard the terrain if any point on the terrain is ‘seen’ by a point in G. Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. We prove that the decision version of this problem is NPhard. This solves a significant open problem and complements recent positive approximability results for the optimization problem.
Our proof uses a reduction from PLANAR 3SAT. We build gadgets capable of ‘mirroring’ a consistent variable assignment back and forth across a main valley. The structural simplicity of 1.5dimensional terrains makes it difficult to build general clause gadgets that do not destroy this assignment when they are evaluated. However, we exploit the structure in instances of PLANAR 3SAT to find very specific operations involving only ‘adjacent’ variables. For these restricted operations we can construct gadgets that allow a full reduction to work.

Thin Partitions: Isoperimetric Inequalities and Sampling
Algorithms for some Nonconvex Families
Karthekeyan Chandrasekaran, Daniel Dadush, Santosh VempalaStarshaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an efficient algorithm for sampling a given starshaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the starshaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over starshaped sets is NPhard.

Inapproximability for planar embedding problems
Jeff Edmonds, Anastasios Sidiropoulos, Anastasios ZouziasWe consider the problem of computing a minimumdistortion bijection between two pointsets in R^2. We prove the first nontrivial inapproximability result for this problem, for the case when the distortion is constant. More precisely, we show that there exist constants 0 < alpha < beta, such that it is NPhard to distinguish between spaces for which the distortion is either at most alpha, or at least beta, under the Euclidean norm. This addresses a question of [Kenyon, Rabani and Sinclair 2004], and extends a result due to [Papadimitriou and Safra 2005], who gave inapproximability for pointsets in R^3.
We also apply similar ideas to the problem of computing a minimum distortion embedding of a finite metric space into R^2. We obtain an analogous inapproximability result under the \ell_{\infty} norm for this problem. Inapproximability for the case of constant distortion was previously known only for dimension at least 3 [Matousek and Sidiropoulos 2008].

How good is the Chord algorithm?
Constantinos Daskalakis, Ilias Diakonikolas, Mihalis YannakakisThe Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjective and parametric optimization, computational geometry, and graphics. We analyze the performance of the chord algorithm, as compared with the optimal approximation that achieves a desired accuracy with the minimum number of points, and prove sharp upper and lower bounds, both in the worst case and average case setting.

Counting Inversions, Offline Orthogonal Range Counting, and Related Problems
Timothy M. Chan, Mihai PatrascuWe give an $O(n\sqrt{\lg n})$time algorithm for counting the number of inversions in a permutation on $n$ elements. This improves a longstanding previous bound of $O(n\lg n/\lg\lg n)$ that followed from Dietz's data structure [WADS'89], and answers a question of Andersson and Petersson [SODA'95]. As Dietz's result is known to be optimal for the related dynamic rank problem, our result demonstrates a significant improvement in the \emph{offline} setting.
Our new technique is quite simple: we perform a ``vertical partitioning'' of a trie (akin to van Emde Boas trees), and use ideas from external memory. However, the technique finds numerous applications: for example, we obtain
 in $d$ dimensions, an algorithm to answer $n$ offline orthogonal range counting queries in time $O(n\lg^{d2+1/d}n)$;
 an improved construction time for online data structures for orthogonal range counting;
 an improved update time for the partial sums problem;
 faster Word RAM algorithms for finding the maximum depth in an arrangement of axisaligned rectangles, and for the slope selection problem.

Graph genus and random partitions
James R. Lee, Anastasios SidiropoulosWe study the quantitative geometry of graphs with small genus. In particular, we exhibit new, optimal random partitioning schemes for such graphs. Using these geometric primitives, we give exponentially improved dependence on genus for a number of problems like approximate maxflow/mincut theorems, approximations for uniform and nonuniform Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds, Lipschitz extension theorems, and various embeddings into normed spaces.

Streaming Algorithms for extent problems in high dimensions
Pankaj K Agarwal, R. SharathkumarWe develop streaming algorithms for maintaining extent measures of a stream S of n points in R^d. We focus on designing streaming algorithms that use polynomial in d (poly(d)) and sublinear in n space. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worstcase approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we design an insertiononly data structure called the blurred ball cover that maintains a set C \subseteq S of $O(1/eps^3 log 1/\eps)$ points. We show that blurred ball cover can be used for answering approximate farthestpoint queries and maintaining approximate minimum enclosing ball and diameter of S. The size of blurred ball cover is linear in d and independent of n.

On the possibility of faster SAT algorithms
Mihai Patrascu and Ryan WilliamsWe investigate the prospects for an algorithm for Boolean CNF satisfiability (CNFSAT) that runs in $O^*(2^{\delta n})$ time for some $\delta < 1$. In such a case we would say CNFSAT has an improved algorithm. We present several hypotheses which we feel are plausible, given current knowledge. We prove that if any of the hypotheses are true, then CNF SAT has an improved algorithm. For other candidate hypotheses, they imply that $k$SAT can be solved in $2^{\delta n}$ time for a fixed $\delta < 1$ that is independent of $k$. Such results would be breakthroughs in exact algorithms. The contrapositive statements show that if we assume satisfiability does not admit improved algorithms, then many interesting lower bounds follow. Our reductions provide tight connections between satisfiability and several foundational problems in logic, graph theory, communication complexity, and computational geometry.

Geometric optimization and sums of algebraic functions
Antoine VigneronWe present a new optimization technique that yields the first FPTAS for several geometric problems. These problems reduce to optimizing a sum of nonnegative, constant descriptioncomplexity algebraic functions. We first give a FPTAS for optimizing such a sum of algebraic functions, and then we apply it to several geometric optimization problems. We obtain the first FPTAS for two fundamental geometric shape matching problems in fixed dimension: maximizing the volume of overlap of two polyhedra under rigid motions, and minimizing their symmetric difference. We obtain the first FPTAS for other problems in fixed dimension, such as computing an optimal ray in a weighted subdivision, finding the largest axially symmetric subset of a polyhedron, and computing minimum area hulls.

Efficient Broadcast on Random Geometric Graphs
Milan Bradonji, Robert Elsässer, Tobias Friedrich, Thomas Sauerwald, Alexandre StaufferA Random Geometric Graph (RGG) in two dimensions is constructed by distributing $n$ nodes uniformly at random in $[0,\sqrt{n}]^2$ and connecting two nodes if their Euclidean distance is at most $r$, for some prescribed $r$. We analyze the following randomized broadcast algorithm on RGGs. At the beginning, there is only one informed node in the largest connected component of the RGG. Then, in each round, each informed node chooses a neighbor uniformly at random and informs it. We prove that this algorithm informs every node in the largest connected component of an RGG within $O(\sqrt{n}/r+\log n)$ rounds with probability $1O(n^{1})$. This holds for any value of $r$ larger than the critical value for the emergence of a connected component with $\Omega(n)$ nodes. By proving this result, we show that for any two nodes sufficiently distant from each other in $[0,\sqrt{n}]^2$, the length of the shortest path between them in the RGG, when such a path exists, has length only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest component of an RGG is $\Theta(\sqrt{n}/r)$, which surprisingly has been an open problem so far.

Maximum Flows and Parametric Shortest Paths in Planar Graphs
Jeff EricksonWe observe that the classical maximum flow problem in any directed planar graph $G$ can be reformulated as a parametric shortest path problem in the oriented dual graph $G^*$. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in $O(n\log n)$ time. As we continuously increase the parameter, each change in the shortest path tree can be effected in $O(\log n)$ time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximumflow algorithm is identical to the recent algorithm of Borradaile and Klein [J. ACM 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change $\Omega(n^2)$ times in the worst case, suggesting that different methods may be required to efficiently compute maximum flows in highergenus graphs.

Road Network Reconstruction for Organizing Paths
Daniel Chen, Leonidas J. Guibas, John Hershberger, Jian SunWe consider the problem of reconstructing a road network from a collection of path traces and provide guarantees to the accuracy of the reconstruction under reasonable assumptions. Our algorithm can be used to process a collection of polygonal paths in the plane so that shared structures (subpaths) among the paths in the collection can be discovered and the collection can be organized to allow efficient path similarity queries against new query paths on the same road network. This is a timely problem, as GPS or other location traces of both people and vehicles are becoming available in a large scale and there is a real need to create appropriate data structures and data bases for such data.

Selfimproving Algorithms for Convex Hulls
Kenneth L. Clarkson, Wolfgang Mulzer, C. SeshadhriWe give an algorithm for computing planar convex hulls in the selfimproving model: Given a sequence I_1, I_2, ... of planar npoint sets, the upper convex hull conv(I) of each set I is desired. We assume that there exists a probability distribution D on sets of n points, such that the inputs I_j are drawn independently according to D. Furthermore, D is such that the individual points in I are distributed independently of each other. In other words, the ith point is distributed according to D_i. The D_i's can be arbitrary but are independent of each other. The distribution D is not known to the algorithm in advance. After a learning phase of n^\eps rounds, the expected time to compute conv(I) is O(n + H(conv(I))). Here, H(conv(I)) is the minimum entropy of any random variable that maps I to a description of conv(I) and to a labeling scheme that proves nonextremality for every point in I not on the hull. This is a lower bound for the expected running time of any algebraic computation tree that computes the convex hull. Our algorithm is therefore asymptotically optimal for D.

Lower bounds for Edit Distance and Product Metrics via PoincareType Inequalities
Alexandr Andoni, T.S. Jayram, Mihai PatrascuWe prove that any sketching protocol for edit distance achieving a constant approximation requires nearly logarithmic (in the strings' length) communication complexity. This is an exponential improvement over the previous, doublylogarithmic, lower bound of [AndoniKrauthgamer, FOCS'07]. Our lower bound also applies to the Ulam distance (edit distance over nonrepetitive strings). In this special case, it is polynomially related to the recent upper bound of [AndoniIndykKrauthgamer, SODA'09].
From a technical perspective, we prove a directsum theorem for sketching product metrics that is of independent interest. We show that, for any metric X that requires sketch size which is a sufficiently large constant, sketching the maxproduct metric \ell_\infty^d(X) requires \Omega(d) bits. The conclusion, in fact, also holds for arbitrary twoway communication. The proof uses a novel technique for information complexity based on Poincar\'e inequalities and suggests an intimate connection between nonembeddability, sketching and communication complexity.

Universal $\epsilon$approximators for integrals
Michael Langberg, Leonard J. SchulmanLet $X$ be a space and $F$ a family of ${0,1}$valued functions on $X$. Vapnik and Chervonenkis showed that if $F$ is "simple" (finite VC dimension), then for every probability measure $\mu$ on $X$ and $\e>0$ there is a finite set $S$ such that for all $f \in F$, $\sum_{x \in S} f(x)/S = [\int f(x) d\mu(x)] \pm \e$.
Think of $S$ as a "universal $\epsilon$approximator" for integration in $F$. $S$ can actually be obtained w.h.p. just by sampling a few points from $\mu$. This is a mainstay of computational learning theory. It was later extended by other authors to families of bounded (e.g., $[0,1]$valued) real functions.
In this work we establish similar "universal $\epsilon$approximators" for families of unbounded nonnegative real functions  in particular, for the families over which one optimizes when performing data classification. In this case the $\epsilon$approximation is multiplicative.

Orthogonal HamSandwich Theorem in R3
Sergey BeregThe hamsandwich theorem states that, given $d\ge 2$ measures in $\R^d$, it is possible to divide all of them in half with a single $(d1)$dimensional hyperplane. We study an orthogonal version of the hamsandwich theorem and define an orthogonal cut using at most $d$ hyperplanes orthogonal to coordinate axes. For example, a hyperplane orthogonal to a coordinate axis is an orthogonal cut. We prove that any three measures in $\R^3$ can be divided in half each with a single orthogonal cut. Applied to point measures, it implies that any three finite sets of points in $\R^3$ can be simultaneously bisected by an orthogonal cut. We present an algorithm for computing an orthogonal hamsandwich cut in $O(n\log n)$ time.
Comments