1,721,054 research outputs found
Recommended from our members
Computing Volumes and Convex Hulls: Variations and Extensions
Full text linkGeometric techniques are frequently utilized to analyze and reason about multi-dimensional data. When confronted with large quantities of such data, simplifying geometric statistics or summaries are often a necessary first step. In this thesis, we make contributions to two such fundamental concepts of computational geometry: Klee's Measure and Convex Hulls. The former is concerned with computing the total volume occupied by a set of overlapping rectangular boxes in d-dimensional space, while the latter is concerned with identifying extreme vertices in a multi-dimensional set of points. Both problems are frequently used to analyze optimal solutions to multi-objective optimization problems: a variant of Klee's problem called the Hypervolume Indicator gives a quantitative measure for the quality of a discrete Pareto Optimal set, while the Convex Hull represents the subset of solutions that are optimal with respect to at least one linear optimization function.In the first part of the thesis, we investigate several practical and natural variations of Klee's Measure Problem. We develop a specialized algorithm for a specific case of Klee's problem called the “grounded” case, which also solves the Hypervolume Indicator problem faster than any earlier solution for certain dimensions. Next, we extend Klee's problem to an uncertainty setting where the existence of the input boxes are defined probabilistically, and study computing the expectation of the volume. Additionally, we develop efficient algorithms for a discrete version of the problem, where the volume of a box is redefined to be the cardinality of its overlap with a given point set.The second part of the thesis investigates the convex hull problem on uncertain input. To this extent, we examine two probabilistic uncertainty models for point sets. The first model incorporates uncertainty in the existence of the input points. The second model extends the first one by incorporating locational uncertainty. For both models, we study the problem of computing the probability that a given point is contained in the convex hull of the uncertain points. We also consider the problem of finding the most likely convex hull, i.e., the mode of the convex hull random variable
Recommended from our members
Geometric Pursuit Evasion
Full text linkIn this dissertation we investigate pursuit evasion problems set in geometric environments. These games model a variety of adversarial situations in which a team of agents, called pursuers, attempts to catch a rogue agent, called the evader. In particular, we consider the following problem: how many pursuers, each with the same maximum speed as the evader, are needed to guarantee a successful capture? Our primary focus is to provide combinatorial bounds on the number of pursuers that are necessary and sufficient to guarantee capture. The first problem we consider consists of an unpredictable evader that is free to move around a polygonal environment of arbitrary complexity. We assume that the pursuers have complete knowledge of the evader's location at all times, possibly obtained through a network of cameras placed in the environment. We show that regardless of the number of vertices and obstacles in the polygonal environment, three pursuers are always sufficient and sometimes necessary to capture the evader. We then consider several extensions of this problem to more complex environments. In particular, suppose the players move on the surface of a 3-dimensional polyhedral body; how many pursuers are required to capture the evader? We show that 4 pursuers always suffice (upper bound), and that 3 are sometimes necessary (lower bound), for any polyhedral surface with genus zero. Generalizing this bound to surfaces of genus g, we prove the sufficiency of (4g + 4) pursuers. Finally, we show that 4 pursuers also suffice under the "weighted region" constraints, where the movement costs through different regions of the (genus zero) surface have (different) multiplicative weights. Next we consider a more general problem with a less restrictive sensing model. The pursuers' sensors are visibility based, only providing the location of the evader if it is in direct line of sight. We begin my making only the minimalist assumption that pursuers and the evader have the same maximum speed. When the environment is a simply-connected (hole-free) polygon of n vertices, we show that Θ(n^1/2 ) pursuers are both necessary and sufficient in the worst-case. When the environment is a polygon with holes, we prove a lower bound of Ω(n^2/3 ) and an upper bound of O(n^5/6 ) pursuers, where n includes the vertices of the hole boundaries. However, we show that with realistic constraints on the polygonal environment these bounds can be drastically improved. Namely, if the players' movement speed is small compared to the features of the environment, we give an algorithm with a worst case upper bound of O(log n) pursuers for simply-connected n-gons and O(√h + log n) for polygons with h holes. The final problem we consider takes a small step toward addressing the fact that location sensing is noisy and imprecise in practice. Suppose a tracking agent wants to follow a moving target in the two-dimensional plane. We investigate what is the tracker's best strategy to follow the target and at what rate does the distance between the tracker and target grow under worst-case localization noise. We adopt a simple but realistic model of relative error in sensing noise: the localization error is proportional to the true distance between the tracker and the target. Under this model we are able to give tight upper and lower bounds for the worst-case tracking performance, both with or without obstacles in the Euclidean plane
Recommended from our members
Multidimensional Team Formation
Full text linkWe consider a team formation problem in multi-dimensional space where the goal is to group a set of n agents into a teams, each of size b, to maximize their total performance. The performance of each team is measured by a score, which is the sum of h highest skill values in each dimension. We wish to maximize the sum of team scores. We prove that the problem is NP-hard if the dimension is d = Omega(log n), even for scoring parameter h=1 and team size b = 4. We then describe an efficient algorithm for solving the problem in two dimensions, as well an algorithm for computing a single optimal team in any constant dimension
Recommended from our members
Geometric Constraint Removal and Related Problems
Full text linkIn a geometric optimization problem, the goal is to optimize an objective functionsubject to a set of constraints induced by a family of geometric objects. When theseconstraints render the problem infeasible or cause the objective function value to be unacceptable,a natural course of action is to remove or relax some of the constraints,without changing the problem formulation too much. In this dissertation, we study some naturalformulations of two geometric optimization problemssubject to a fixed budget on the number of constraints that can be removed.For most parts, our focus is on path finding problems in the plane in presence of polygonal obstacles,where we are allowed to remove a small number of the obstacles. We first consider the case whenobstacles are overlapping such that no "feasible" path between a given source s and destination t exists.Here, one would like to remove the minimum number of obstacles so that there exists an obstacle-free s--t path.This problem is more commonly known as minimum constraint removal (MCR), and is known to be NP-hard,even when obstacles are axis-aligned rectangles. We design approximation algorithms for MCR, which are basedon solving the related problem of computing a minimum color path in a colored graph.Next, we consider the case when obstacles are disjoint (so a feasible path always exists) but even the shortest suchpath is unacceptably long. For this case, we design polynomial-time algorithms to compute a set of at most k obstaclesremoving which reduces the original shortest path by maximum amount. An important requirement is that the obstacles must beconvex polygons.Finally, we consider another geometric optimization problem called maximum exposure.Here, we are given a set of points P and a set of ranges R covering them,and we would like to remove a subset of R with at most k ranges so as to `expose' (or uncover)a maximum number of points. Our work here deals with designing approximation algorithms
Online Minimum Spanning Trees with Weight Predictions
Full text linkWe consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Then the actual weights arrive one at a time and an irrevocable decision must be made regarding whether or not the edge should be included into the spanning tree. In order to assess the quality of our algorithms, we define an appropriate error measure and analyze the performance of the algorithms as a function of the error. We prove that, according to competitive analysis, the simplest algorithm, Follow-the-Predictions, is optimal. However, intuitively, one should be able to do better, and we present a greedy variant of Follow-the-Predictions. In analyzing that algorithm, we believe we present the first random order analysis of a non-trivial online algorithm with predictions, by which we obtain an algorithmic separation. This may be useful for distinguishing between algorithms for other problems when Follow-the-Predictions is optimal according to competitive analysis.We consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Then the actual weights arrive one at a time and an irrevocable decision must be made regarding whether or not the edge should be included into the spanning tree. In order to assess the quality of our algorithms, we define an appropriate error measure and analyze the performance of the algorithms as a function of the error. We prove that, according to competitive analysis, the simplest algorithm, Follow-the-Predictions, is optimal. However, intuitively, one should be able to do better, and we present a greedy variant of Follow-the-Predictions. In analyzing that algorithm, we believe we present the first random order analysis of a non-trivial online algorithm with predictions, by which we obtain an algorithmic separation. This may be useful for distinguishing between algorithms for other problems when Follow-the-Predictions is optimal according to competitive analysis.</p
Block Crossings in One-Sided Tanglegrams
No full textTanglegrams are drawings of two rooted binary phylogenetic trees and a matching between their leaf sets. The trees are drawn crossing-free on opposite sides with their leaf sets facing each other on two vertical lines. Instead of minimizing the number of pairwise edge crossings, we consider the problem of minimizing the number of block crossings, that is, two bundles of lines crossing each other locally. With one tree fixed, the leaves of the second tree can be permuted according to its tree structure. We give a complete picture of the algorithmic complexity of minimizing block crossings in one-sided tanglegrams by showing NP -completeness, constant-factor approximations, and a fixed-parameter algorithm. We also state first results for non-binary trees
Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs
No full textIn this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters -- maximum independent set, minimum dominating set and maximum matching -- on sparse graph classes, i.e., graphs which satisfy m=O(n) where m,n is the number of edges, vertices respectively. Each of the three graph parameters we consider can have size Ω(n) even on sparse graph classes, and hence for sublinear-space algorithms we are restricted to parameter estimation instead of attempting to find a solution.We obtain these results:– Estimating Max Independent Set via the Caro-Wei bound: Caro and Wei each showed λ = Σv 1/(d(v) + 1) is a lower bound on max independent set size, where vertex v has degree d(v). If average degree, d‾, is 𝒪(1), and max degree Δ = 𝒪(ε2 d‾-3 n), our algorithms, with at least 1 - δ success probability:• In online streaming, return an actual independent set of size 1 ± ε times λ. This improves on Halldórsson et al. [Algorithmica '16]: we have less working space, i.e., 𝒪(log ε-1·log n·log δ-1), faster updates, i.e., 𝒪(log ε-1), and bounded success probability.• In insertion-only streams, approximate λ within factor 1 ± ε, in one pass, in 𝒪(d‾ ε-2 log n·log δ-1) space. This aligns with the result of Cormode et al. [ISCO '18], though our method also works for online streaming. In a vertex-arrival and random-order stream, space reduces to 𝒪(log(d‾ ε-1)). With extra space and post-processing step, we remove the max-degree constraint.– Sublinear-Space Algorithms on Forests: On a forest, Esfandiari et al. [SODA '15, TALG '18] showed space lower bounds for 1-pass randomized algorithms that approximately estimate these graph parameters. We narrow the gap between upper and lower bounds:• Max independent set size within 3/2·(1±ε) in one pass and in log𝒪(1) n space, and within 4/3·(1±ε) in two passes and in 𝒪‾(√n) space; the lower bound is for approx. ≤ 4/3.• Min dominating set size within 3·(1±ε) in one pass and in log𝒪(1) n space, and within 2·(1±ε) in two passes and in 𝒪‾(√n) space; the lower bound is for approx. ≤ 3/2.• Max matching size within 2·(1±ε) in one pass and in log𝒪(1) n space, and within 3/2·(1±ε) in two passes and in 𝒪‾(√n) space; the lower bound is for approx. ≤ 3/2.<br/
Recommended from our members
Algorithmic Problems in Committee Selection
Full text linkCommittee selection is a classical problem in the social sciences where the goal is to choose a fixed number of candidates based on voters’ preferences. The problem naturally models elections in representative democracies or hiring of staff, but also generalizes many other resource allocation problems such as the classical facility location problems where facilities are treated as candidates and users as voters. By explicitly modeling voters’ preferences, the committee selection problem raises a number of interesting and challenging algorithmic problems such as winner determination, fault tolerance, and fairness. In this dissertation, we study four such problems.For the most part, we consider the committee selection problem in Euclidean d-space where candidates/voters are points and voters’ preferences are implicitly derived using their Euclidean distances to the candidates. Our first problem is to find a winning committee under the well-known Chamberlin-Courant voting rule. The goal here is to choose a committee of k candidates so that the rank of any voter’s most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical k-center problem.) We show that the problem is NP-hard in any dimension d ≥ 2, and is also hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with a good minimax score.Our second problem deals with fault tolerance in committee selection. We study the following three variants: (1) given a committee and a set of f failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of f candidates; and (3) design a committee with the best replacement score under worst-case failures. Our main results are polynomial-time algorithms for three problems in one dimension. We also show that the problems are NP-hard in higher dimensions and give constant-factor approximations for all three problems along with an FPT bicriterion approximation for the optimal committee problem. In our third problem we consider non-Euclidean elections and study the following two natural questions for a given election: (1) (Winner Verification) Given a subset of candidates (committee) T, is T a winning committee? (2) (Candidate Winner) Given a candidate c, does c belong to a winning committee? We show that both the above problems are hard (coNP-complete and θ_{2}^{P}-complete, respectively) in general, but for the restricted case of single-peaked and single-crossing preferences, they admit efficient algorithms.Our last problem is the problem of covering a multicolored set of points in R^d using (at most) k disjoint unit-radius balls chosen from a candidate set of unit-radius balls so that each color class is covered fairly in proportion to its size. Specifically, we investigate the complexity of covering the maximum number of points in this setting. In the committee selection terminology, each ball is a candidate and each point is a voter; a voter approves all candidates within a unit-radius ball around it, and our goal is to choose an optimal size k committee under fairness constraints. We show that the problem is NP-hard even in one dimension when the number of colors is not fixed. On the other hand, for a fixed number of colors, we present a polynomial-time exact algorithm in one dimension, and a PTAS in any fixed dimension d ≥ 2
Realizability Makes A Difference: A Complexity Gap For Sink-Finding in USOs
No full textISSN:0302-9743ISSN:1611-3349ISSN:1611-334
Density Approximation for Moving Groups
Full text linkSets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving group. We use kernel density estimation to model the density within a group and show how to efficiently maintain an approximation of this density description over time. Furthermore, we track persistent maxima which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently.</p
- …
