waashk/dblp huggingface dataset:
maintaining approximate extent measures of moving points. we present approximation algorithms for maintaining various descriptors of the extent of moving points in rd. we first describe a data structure for maintaining the smallest orthogonal rectangle containing the point set. we then use this data structure to maintain the approximate diameter, smallest enclosing disk, width, and smallest area or perimeter bounding rectangle of a set of moving points in r2 so that the number of events is only a constant. this contrasts with &ohgr;(n2) events that data structures for the maintenance of those exact properties have to handle.
computing steiner minimum trees in hamming metric. computing steiner minimum trees in hamming metric is a well studied problem that has applications in several fields of science such as computational linguistics and computational biology. among all methods for finding such trees, algorithms using variations of a branch and bound method developed by penny and hendy have been the fastest for more than 20 years. in this paper we describe a new pruning approach that is superior to previous methods and its implementation.
robust shape fitting via peeling and grating coresets. let p be a set of n points in &#x211d; d . a subset $\mathcal {s}$ of p is called a (k,&#x03b5;)-kernel if for every direction, the directional width of $\mathcal {s}$ &#x03b5;-approximates that of p, when k &#x201c;outliers&#x201d; can be ignored in that direction. we show that a (k,&#x03b5;)-kernel of p of size o(k/&#x03b5;(d&#x2212;1)/2) can be computed in time o(n+k2/&#x03b5;d&#x2212;1). the new algorithm works by repeatedly &#x201c;peeling&#x201d; away (0,&#x03b5;)-kernels from the point set. we also present a simple &#x03b5;-approximation algorithm for fitting various shapes through a set of points with at most k outliers. the algorithm is incremental and works by repeatedly &#x201c;grating&#x201d; critical points into a working set, till the working set provides the required approximation. we prove that the size of the working set is independent of n, and thus results in a simple and practical, near-linear &#x03b5;-approximation algorithm for shape fitting with outliers in low dimensions. we demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems.
relative neighborhood graphs in three dimensions. the relative neighborhood graph (rng) of a set s of n points in r is a graph (s, e), where (p, q) &egr; e if and only if there is no point z &egr; s such that max {d(p, z), d(q,z)} < d(p,q). we show that in r , rng(s) has o(n4/3) edges. we present a randomized algorithm that constructs rng(s) in expected time o(n3/2+&egr;) assuming that the points of s are in general position. if the points of s are arbitrary, the expected running time is o(n7/4+&egr;). these algorithms can be made deterministic without affecting their asymptotic running time.
computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks. let s be a set of n points in r2. given an integer 1 &le; k &le; n, we wish to find a maximally separated subset i &sube; s of size k; this is a subset for which the minimum among the (k2) pairwise distances between its points is as large as possible. the decision problem associated with this problem is to determine whether there exists i &sube; s, |i| = k, so that all (k2) pairwise distances in i are at least 2, say. this problem can also be formulated in terms of disk-intersection graphs: let d be the set of unit disks centered at the points of s. the disk-intersection graph g of d connects pairs of disks by an edge if they have nonempty intersection. i is then the set of centers of disks that form an independent set in the graph g. this problem is known to be np-complete if k is part of the input.in this paper we first present a linear-time approximation algorithm for any constant k. next we give o(n4/3polylog(n)) exact algorithms for the cases k = 3 and k = 4. we also present a simpler no(&radic;k)-time algorithm (as compared with the recent algorithm in [5]) for arbitrary values of k.
approximation algorithms for projective clustering. we consider the following two instances of the projective clustering problem: given a set s of n points in rd and an integer k > 0, cover s by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. let w* be the smallest value so that s can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w*. this paper contains three main results: (i) for d = 2, we present a randomized algorithm that computes o(k log k) strips of width at most w* that cover s. its expected running time is o(nk2log4n) if k2 log k ≤ n; for larger values of k, the expected running time is o(n2/3k8/3log14/3n). (ii) for d = 3, a cover of s by o(k log k) slabs of width at most w* can be computed in expected time o(n3/2k9/4polygon(n)).(iii) we compute a cover of s ⊂ rd by o(dk log k) d-cylinders of diameter at most 8w* in expected time o(dnk3 log4 n). we also present a few extensions of this result.
coins make quantum walks faster. we show how to search n items arranged on a &radic;n &times; &radic;n grid in time o(&radic;n log n), using a discrete time quantum walk. this result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom. since it has been shown recently that such a continuous time walk needs time &omega;(n) to perform the same task. our result improves on a previous bound for quantum local search by aaronson and ambainis. we generalize our result to 3 and more dimensions where the walk yields the optimal performance of o(&radic;n) and give several extensions of quantum walk search algorithms and generic expressions for its performance for general graphs. the coin-flip operation needs to be chosen judiciously: we show that another "natural" choice of coin gives a walk that takes &omega;(n) steps. we also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time o(&radic;n log n).
finding a line transversal of axial objects in three dimensions. an axial object in e3 is a box or rectangle, all of whose edges are parallel to the coordinate axes. a line transveral of a set of axial objects is a line that intersects every object. we present an algorithm which finds a line transversal, if one exists, in expected linear time. in the process, we generalize a randomized linear programming algorithm, and prove that the set of line transversals of axial objects has a constant number of connected components.
the hunting of the bump: on maximizing statistical discrepancy. anomaly detection has important applications in biosurveilance and environmental monitoring. when comparing measured data to data drawn from a baseline distribution, merely, finding clusters in the measured data may not actually represent true anomalies. these clusters may likely be the clusters of the baseline distribution. hence, a discrepancy function is often used to examine how different measured data is to baseline data within a region. an anomalous region is thus defined to be one with high discrepancy.in this paper, we present algorithms for maximizing statistical discrepancy functions over the space of axis-parallel rectangles. we give provable approximation guarantees, both additive and relative, and our methods apply to any convex discrepancy function. our algorithms work by connecting statistical discrepancy to combinatorial discrepancy; roughly speaking, we show that in order to maximize a convex discrepancy function over a class of shapes, one needs only maximize a linear discrepancy function over the same set of shapes.we derive general discrepancy functions for data generated from a one- parameter exponential family. this generalizes the widely-used kulldorff scan statistic for data from a poisson distribution. we present an algorithm running in o(1/&epsilon; n2 log2n) that computes the maximum discrepancy rectangle to within additive error &epsilon;, for the kulldorff scan statistic. similar results hold for relative error and for discrepancy functions for data coming from gaussian, bernoulli, and gamma distributions. prior to our work, the best known algorithms were exact and ran in time o(n4).
pseudo-line arrangements: duality, algorithms, and applications. a finite collection of x-monotone unbounded jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each other there. let l be such a collection of n pseudo-lines, and let p be a set of m points in $\reals^2$. extending a result of goodman [discrete math., 32 (1980), pp. 27--35], we define a duality transform that maps l to a set l* of points in $\reals^2$ and p to a set p* of (x-monotone) pseudo-lines in $\reals^2$, so that the incidence and the "above-below" relations between the points and the pseudo-lines are preserved. we present an efficient algorithm for computing the dual arrangement {\eus a}$(p^*)$ under an appropriate model of computation. we also present a dynamic data structure for reporting, in $o(m^\eps + k)$ time, all k points of p that lie below a query arc, which is either a circular arc or a portion of the graph of a polynomial of fixed degree. this result is needed for computing the dual arrangement for certain classes of pseudo-lines arising in several applications, but is also interesting in its own right. we present a few applications of our dual arrangement algorithm, such as computing incidences between points and pseudo-lines and computing a subset of faces in a pseudo-line arrangement.next, we present an efficient algorithm for cutting a set of circles into arcs so that every pair of arcs intersect in at most one point, i.e., the resulting arcs constitute a collection of pseudo-segments. by combining this algorithm with our algorithm for computing the dual arrangement of pseudo-lines, we obtain efficient algorithms for several problems involving arrangements of circles or circular arcs, such as reporting or counting incidences between points and circles and computing a set of marked faces in arrangements of circles.
pattern matching with address errors: rearrangement distances. historically, approximate pattern matching has mainly focused at coping with errors in the data, while the order of the text/pattern was assumed to be more or less correct. in this paper we consider a class of pattern matching problems where the content is assumed to be correct, while the locations may have shifted/changed. we formally define a broad class of problems of this type, capturing situations in which the pattern is obtained from the text by a sequence of rearrangements. we consider several natural rearrangement schemes, including the analogues of the @?"1 and @?"2 distances, as well as two distances based on interchanges. for these, we present efficient algorithms to solve the resulting string matching problems.
two-dimensional periodicity and its applications. string matching is rich with a variety of algorithmic tools. in contrast, multidimensional matching has a rather sparse set of techniques. this paper presents a new algorithmic technique for two-dimensional matching, that of periodicity analysis. periodicity in strings has been used to solve string matching problems. the success of these algorithms suggests that periodicity can be as important a tool in multidimensional matching. however, multidimensional periodicity is not as simple as it is in strings and was not formally studied or used in pattern matching. this paper's main contribution is defining and analysing two-dimensional periodicity in rectangular arrays. in addition, we introduce a new pattern matching paradigm - compressed matching. a text array t and a pattern array p are given in compressed forms c(t) and c(p). we seek all appearances of p in t, without decompressing t. by using periodicity analysis, we show that for the two-dimensional run-length compression there is a o(|c(t)|log|p|+|p|), or almost optimal algorithm that can achieve a search time that is sublinear in the size of the text |t|.
surface approximation and geometric partitions. motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: given a set s of n points sampled from a bivariate function f(x,y) and an input parameter $\eps > 0$, compute a piecewise-linear function $\sigma(x,y)$ of minimum complexity (that is, an xy-monotone polyhedral surface, with a minimum number of vertices, edges, or faces) such that $| \sigma(x_p, y_p) \; - \; z_p | \:\:\leq\:\: \eps$ for all $(x_p, y_p, z_p) \in s$. we give hardness evidence for this problem, by showing that a closely related problem is np-hard. the main result of our paper is a polynomial-time approximation algorithm that computes a piecewise-linear surface of size o(ko log ko), where ko is the complexity of an optimal surface satisfying the constraints of the problem.the technique developed in our paper is more general and applies to several other problems that deal with partitioning of points (or other objects) subject to certain geometric constraints. for instance, we get the same approximation bound for the following problem arising in machine learning: given n "red" and m "blue" points in the plane, find a minimum number of pairwise disjoint triangles such that each blue point is covered by some triangle and no red point lies in any of the triangles.
applications of parametric searching in geometric optimization. we present several applications in computational geometry of megiddo's parametric searching technique. these applications include; (1) finding the minimum hausdorff distance in the euclidean metric between two polygonal regions under translation; (2) computing the biggest line segment that can be placed inside a simple polygon; (3) computing the smallest width annulus that can contain a given set of points in the plane; (4) solving the 1-segment center problem&mdash;given a set of points in the plane, find a placement for a given line segment (under translation and rotation) which minimizes the largest distance from the segment to the given points; (5) given a set of n points in 3-space, finding the largest radius r such that if we place a ball of radius r around each point, no segment connecting a pair of points is intersected by a third ball. besides obtaining efficient solutions to all these problems (which, in every case, either improve considerably previous solutions or are the first non-trivial solutions to these problems), our goal is to demonstrate the versatility of the parametric searching technique.
lower bound for sparse euclidean spanners. given a one-dimensional graph g such that any two consecutive nodes are unit distance away, and such that the minimum number of links between any two nodes (the diameter of g) is o(log n), we prove an &omega;(n log n/log log n) lower bound on the sum of lengths of all the edges (i.e., the weight of g). the problem is a variant of the widely studied partial sum problem. this in turn provides a lower bound on euclidean spanner graphs with small diameter and low weight, showing that the upper bound from [1] is almost tight.
self-improving algorithms. we investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an arbitrary, unknown input distribution. we give such self-improving algorithms for sorting and clustering. the highlights of this work: (i) a sorting algorithm with optimal expected limiting running time; and (ii) a k-median algorithm over the hamming cube with linear expected limiting running time. in all cases, the algorithm begins with a learning phase during which it adjusts itself to the input distribution (typically in a logarithmic number of rounds), followed by a stationary regime in which the algorithm settles to its optimized incarnation.
optimal parallel selection. we present an optimal parallel selection algorithm on the erew pram. this algorithm runs in o(log n) time with n/log n processors. this complexity matches the known lower bound for parallel selection on the erew pram model. we therefore close this problem which has been open for more than a decade.
overlap matching. we propose a new paradigm for string matching, namely structural matching. in structural matching, the text and pattern contents are not important. rather, some areas in the text and patterns are singled out, say intervals. a &ldquo;match&rdquo; is a text location where a specified relation between the text and pattern areas is satisfied. in particular we define the structural matching problem of overlap (parity) matching. we seek the text locations where all overlaps of the given pattern and text intervals have even length. we show that this problem can be solved in time &ogr;(n log m), where the text length is n and the pattern length is m. as an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. the string matching with swaps problem is the problem of string matching in the presence of local swaps. the best known deterministic upper bound for this problem was &ogr;(nm1/3 log m log &sgr;) for a general alphabet &sum;, where &sgr; = min(m, &brvbar;&sum;&brvbar;). our reduction provides a solution to the pattern matching with swaps problem in time &ogr;(n log m log &sgr;).
bipartite roots of graphs. graph h is a root of graph g if there exists a natural number k such that xy &isin; e(g) &harr; dh(x, y) &le; k where dh(x, y) is the length of a shortest path in h from x to y. in such a case, h is a k-th root of g and we write g = hk and call g the k-th power of h. motwani and sudan proved that it is np-complete to recognize squares of graphs and believed it is also np-complete to recognize squares of bipartite graphs. in this paper, we show, rather surprisingly, that squares of bipartite graphs can be recognized in polynomial time. also, we show that counting the number of different bipartite square roots of a graph can be done in polynomial time although this number could be exponential in the size of the input graph. furthermore, we can generate all bipartite roots of a graph g in time o(max{&delta;(g) &middot; m, r(g)}) where &delta;(g) is the maximum degree of g, m is the time complexity to do matrix multiplication, and r(g) is the number of different bipartite square roots of g. by using the tools developed, we are able to give a new and simpler linear time algorithm to recognize squares of trees and a new algorithmic proof that tree square roots, when they exist, are unique up to isomorphism. finally, we prove the np-completeness of recognition of cubes of bipartite graphs.
the angular-metric traveling salesman problem. motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a tsp tour for a set of points in euclidean space, where the angle cost of a tour is the sum of the direction changes at the points. we establish the np-hardness of both this problem and its relaxation to the cycle cover problem. we then consider the issue of designing approximation algorithms for these problems and show that both problems can be approximated to within a ratio of o(log n) in polynomial time. we also consider the problem of simultaneously approximating both the angle and the length measure for a tsp tour. in studying the resulting tradeoff, we choose to focus on the sum of the two performance ratios and provide tight bounds on the sum. finally, we consider the extremal value of the angle measure and obtain essentially tight bounds for it. in this paper we restrict our attention to the planar setting, but all our results are easily extended to higher dimensions.
complexities for generalized models of self-assembly. in this paper, we extend rothemund and winfree's examination of the tile complexity of tile self-assembly [6]. they provided a lower bound of &omega;(log n/log log n) on the tile complexity of assembling an n &times; n square for almost all n. adleman et al. [1] gave a construction which achieves this bound. we consider whether the tile complexity for self-assembly can be reduced through several natural generalizations of the model. one of our results is a tile set of size o(&radic;log n) which assembles an n &times; n square in a model which allows flexible glue strength between non-equal glues (this was independently discovered in [3]). this result is matched by a lower bound dictated by kolmogorov complexity. for three other generalizations, we show that the &omega;(log n/log log n) lower bound applies to n &times; n squares. at the same time, we demonstrate that there are some other shapes for which these generalizations allow reduced tile sets. specifically, for thin rectangles with length n and width k, we provide a tighter lower bound of &omega;(n(1/k)/k) for the standard model, yet we also give a construction which achieves o(log n/log log n) complexity in a model in which the temperature of the tile system is adjusted during assembly. we also investigate the problem of verifying whether a given tile system uniquely assembles into a given shape, and show that this problem is np-hard.
faster algorithms for string matching with mismatches. the string matching with mismatches problem is that of finding the number of mismatches between a pattern p of length m and every length m substring of the text t. currently, the fastest algorithms for this problem are the following. the galil-giancarlo algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time o(nk). the abrahamson algorithm finds the number of mismatches at every location in time o(n√ m log m). we present an algorithm that is faster than both. our algorithm finds all locations where the pattern has at most k errors in time o(n√k log k). we also show an algorithm that solves the above problem in time o((n + (nk3)/m) log k).
knapsack auctions. we consider a game theoretic knapsack problem that has application to auctions for selling advertisements on internet search engines. consider n agents each wishing to place an object in the knapsack. each agent has a private valuation for having their object in the knapsack and each object has a publicly known size. for this setting, we consider the design of auctions in which agents have an incentive to truthfully reveal their private valuations. following the framework of goldberg et al. [10], we look to design an auction that obtains a constant fraction of the profit obtainable by a natural optimal pricing algorithm that knows the agents' valuations and object sizes.we give an auction that obtains a constant factor approximation in the non-trivial special case where the knapsack has unlimited capacity. we then reduce the limited capacity version of the problem to the unlimited capacity version via an approximately efficient auction (i.e., one that maximizes the social welfare). this reduction follows from generalizable principles.