Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Algorithmic Techniques for Several Multidimensional Geometric Data Management and Analysis Problems
150
0
0.0
(
0
)
Added by
Mugurel Ionut Andreica
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Mugurel Ionut Andreica
Ask ChatGPT about the research
No Arabic abstract
In this paper I present several novel, efficient, algorithmic techniques for solving some multidimensional geometric data management and analysis problems. The techniques are based on several data structures from computational geometry (e.g. segment tree and range tree) and on the well-known sweep-line method.
rate research
Read More
In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials calF = {P_1,...,P_m} to a new collection calF so that the polynomials in calF are pseudorandom. These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from calF to calF is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection calF. In particular, when the field is of high characteristic, in polynomial time, we can refine calF into calF where every nonzero linear combination of polynomials in calF has desirably small Gowers norm. Using the algorithmic regularity lemmas, we show that if a polynomial P of degree d is within (normalized) Hamming distance 1-1/|F| -eps of some unknown polynomial of degree k over a prime field F (for k < d < |F|), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/|F| -eta of P, for some eta depending on eps. This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius (finding one close codeword), when the received word P itself is a polynomial of degree d (with k < d < |F|). We also obtain an algorithmic version of the worst-case to average-case reductions by Kaufman and Lovett. They show that if a polynomial of degree d can be weakly approximated by a polynomial of lower degree, then it can be computed exactly using a collection of polynomials of degree at most d-1. We give an efficient (randomized) algorithm to find this collection.
In the Art Gallery Problem we are given a polygon $Psubset [0,L]^2$ on $n$ vertices and a number $k$. We want to find a guard set $G$ of size $k$, such that each point in $P$ is seen by a guard in $G$. Formally, a guard $g$ sees a point $p in P$ if the line segment $pg$ is fully contained inside the polygon $P$. The history and practical findings indicate that irrational coordinates are a very rare phenomenon. We give a theoretical explanation. Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude $delta$ of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an $existsmathbb{R}$-complete problem was analyzed by Smoothed Analysis.
In this paper, we consider the Minimum-Load $k$-Clustering/Facility Location (MLkC) problem where we are given a set $P$ of $n$ points in a metric space that we have to cluster and an integer $k$ that denotes the number of clusters. Additionally, we are given a set $F$ of cluster centers in the same metric space. The goal is to select a set $Csubseteq F$ of $k$ centers and assign each point in $P$ to a center in $C$, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have a rich literature, the minimum-load objective is not studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [ACM Trans. Algo. 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is $O(k)$, even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017], which generalizes MLkC. Here the input points are colored by one of the $ell$ colors denoting the group they belong to. MLkC is the special case with $ell=1$. Considering this problem, we are able to obtain a $3$-approximation in $f(k,ell)cdot n^{O(1)}$ time. Also, our scheme leads to an improved $(1 + epsilon)$-approximation in case of Euclidean norm, and in this case, the running time depends only polynomially on the dimension $d$. Our results imply the same approximations for MLkC with running time $f(k)cdot n^{O(1)}$, achieving the first constant approximations for this problem in general and Euclidean metric spaces.
We introduce polyhedra circuits. Each polyhedra circuit characterizes a geometric region in $mathbb{R}^d$. They can be applied to represent a rich class of geometric objects, which include all polyhedra and the union of a finite number of polyhedra. They can be used to approximate a large class of $d$-dimensional manifolds in $mathbb{R}^d$. Barvinok developed polynomial time algorithms to compute the volume of a rational polyhedra, and to count the number of lattice points in a rational polyhedra in a fixed dimensional space $mathbb{R}^d$ with a fix $d$. Define $T_V(d,, n)$ be the polynomial time in $n$ to compute the volume of one rational polyhedra, $T_L(d,, n)$ be the polynomial time in $n$ to count the number of lattice points in one rational polyhedra with $d$ be a fixed dimensional number, $T_I(d,, n)$ be the polynomial time in $n$ to solve integer linear programming time with $d$ be the fixed dimensional number, where $n$ is the total number of linear inequalities from input polyhedra. We develop algorithms to count the number of lattice points in the geometric region determined by a polyhedra circuit in $Oleft(ndcdot r_d(n)cdot T_V(d,, n)right)$ time and to compute the volume of the geometric region determined by a polyhedra circuit in $Oleft(ncdot r_d(n)cdot T_I(d,, n)+r_d(n)T_L(d,, n)right)$ time, where $n$ is the number of input linear inequalities, $d$ is number of variables and $r_d(n)$ be the maximal number of regions that $n$ linear inequalities with $d$ variables partition $mathbb{R}^d$.
This is the arXiv index for the electronic proceedings of GD 2019, which contains the peer-reviewed and revised accepted papers with an optional appendix. Proceedings (without appendices) are also to be published by Springer in the Lecture Notes in Computer Science series.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
