Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SIAM Journal on Computing, 53(4), 1002-1038, 2024.
@article{coveringsjournal,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
title = {Economical Convex Coverings and Applications},
journal = {SIAM Journal on Computing},
volume = {53},
number = {4},
pages = {1002--1038},
doi = {10.1137/23M1568351},
year = {2024},
url = {https://arxiv.org/abs/2303.08349},
}
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ε > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an $ε$ expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ε-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size nO(n) / ε(n-1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the Lp unit ball, this bound has been improved to 2O(n) / ε(n-1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. As an additional consequence, we obtain the fastest (1+ε)-approximate CVP algorithm that works in any norm, with a running time of 2O(n) / ε(n-1)/2 up to polynomial factors in the input size, and we obtain the fastest (1+ε)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of 2O(n)).
Guilherme D. da Fonseca and Yan Gerard; invited as CG:SHOP paper of SoCG 2024, 84:1-9, 2024.
The source code is available at github.com/gfonsecabr/shadoks-CGSHOP2024.
@inproceedings{CGSHOP24conf,
author = {Guilherme D. da Fonseca and Yan Gerard},
title = {Shadoks Approach to Knapsack Polygonal Packing},
booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)},
series = {LIPIcs},
volume = {293},
pages = {84:1--84:9},
year = {2024},
doi = {10.4230/LIPIcs.SoCG.2024.84},
url = {https://arxiv.org/abs/2403.20123},
}
We describe the heuristics used by the Shadoks team in the CG:SHOP 2024 Challenge. Each instance consists of a convex polygon called container and a multiset of items, where each item is a simple polygon and has an associated value. The goal is to pack some of the items inside the container using translations, in order to maximize the sum of their values. Our strategy consists of obtaining good initial solutions and improving them with local search. To obtain the initial solutions we used integer programming and a carefully designed greedy approach.
Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier; accepted to WALCOM 2024, 163-178, 2024.
@inproceedings{shortuntangleconf,
author = {Guilherme D. da Fonseca and Yan Gerard and Bastien Rivier},
title = {Short Flip Sequences to Untangle Segments in the Plane},
booktitle = {International Conference and Workshops on Algorithms and Computation (WALCOM 2024)},
series = {Lecture Notes in Computer Science},
volume = {14549},
pages = {163--178},
year = {2024},
doi = {10.1007/978-981-97-0566-5_13},
url = {https://arxiv.org/abs/2307.00853},
}
A (multi)set of segments in the plane may form a TSP tour, a matching, a tree, or any multigraph. If two segments cross, then we can reduce the total length with the following flip operation. We remove a pair of crossing segments, and insert a pair of non-crossing segments, while keeping the same vertex degrees. The goal of this paper is to devise efficient strategies to flip the segments in order to obtain crossing-free segments after a small number of flips. Linear and near-linear bounds on the number of flips were only known for segments with endpoints in convex position. We generalize these results, proving linear and near-linear bounds for cases with endpoints that are not in convex position. Our results are proved in a general setting that applies to multiple problems, using multigraphs and the distinction between removal and insertion choices when performing a flip.
Guilherme D. da Fonseca; invited as CG:SHOP paper of SoCG 2023, 67:1-9, 2023.
The source code is available at github.com/gfonsecabr/shadoks-CGSHOP2023.
@inproceedings{CGSHO23conf,
author = {Guilherme D. da Fonseca},
title = {Shadoks Approach to Convex Covering},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
series = {LIPIcs},
volume = {258},
pages = {67:1--67:9},
year = {2023},
url = {https://arxiv.org/abs/2303.07696},
doi = {10.4230/LIPIcs.SoCG.2023.67},
}
We describe the heuristics used by the Shadoks team in the CG:SHOP 2023 challenge. The challenge consists of 206 instances, each being a polygon with holes. The goal is to cover each instance polygon by a small number of convex polygons. Our general strategy is the following. We find a big collection of large (often maximal) convex polygons inside the instance polygon and then solve several set cover problems to find a small subset of the collection that covers the whole polygon.
Loïc Crombez, Guilherme D. da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng; CG:SHOP 2022 special issue of ACM Journal of Experimental Algorithmics, 28, 1.2, 1-13, 2023.
@article{CGSHOP22journal,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Florian Fontan and Yan Gerard and Aldo Gonzalez-Lorenzo and Pascal Lafourcade and Luc Libralesso and Benjamin Momege and Jack Spalding-Jamieson and Brandon Zhang and Da Wei Zheng},
journal = {ACM Journal of Experimental Algorithmics},
title = {Conflict Optimization for Binary {CSP} Applied to Minimum Partition into Plane Subgraphs and Graph Coloring},
pages = {1--13},
volume = {28},
articleno = {1.2},
doi = {10.1145/3588869},
url = {https://arxiv.org/abs/2303.09632},
year = {2023},
}
CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the top three teams used the same technique, called conflict optimization. This technique has been introduced in the 2021 edition of the challenge, to solve a coordinated motion planning problem. In this paper, we present the technique in the more general framework of binary constraint satisfaction problems (binary CSP). Then, the top three teams describe their different implementations of the same underlying strategy. We evaluate the performance of those implementations to vertex color not only geometric graphs, but also other types of graphs.
Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier; EuroCG 2022 special issue of Computational Geometry: Theory and Applications, 111:101974, 2023.
@article{untanglejournal,
author = {Arun Kumar Das and Sandip Das and Guilherme D. da Fonseca and Yan Gerard and Bastien Rivier},
title = {Complexity Results on Untangling Red-Blue Matchings},
journal = {Computational Geometry},
volume = {111},
pages = {101974},
year = {2023},
doi = {10.1016/j.comgeo.2022.101974},
url = {https://arxiv.org/abs/2202.11857},
}
Given a matching between n red points and n blue points by line segments in the plane, we consider the problem of obtaining a crossing-free matching through flip operations that replace two crossing segments by two non-crossing ones. We first show that (i) it is NP-hard to alpha-approximate the shortest flip sequence, for any constant alpha. Second, we show that when the red points are colinear, (ii) given a matching, a flip sequence of length at most n(n-1)/2 always exists, and (iii) the number of flips in any sequence never exceeds (n(n-1)/2) (n+4)/6. Finally, we present (iv) a lower bounding flip sequence with roughly 1.5 n(n-1)/2 flips, which shows that the n(n-1)/2 flips attained in the convex case are not the maximum, and (v) a convex matching from which any flip sequence has roughly 1.5 n flips. The last four results, based on novel analyses, improve the constants of state-of-the-art bounds.
Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier; WALCOM 2023, 102-112, 2023.
@inproceedings{longestuntangleconf,
author = {Guilherme D. da Fonseca and Yan Gerard and Bastien Rivier},
title = {On the Longest Flip Sequence to Untangle Segments in the Plane},
booktitle = {International Conference and Workshops on Algorithms and Computation (WALCOM 2023)},
series = {Lecture Notes in Computer Science},
volume = {13973},
pages = {102--112},
year = {2023},
doi = {10.1007/978-3-031-27051-2_10},
url = {https://arxiv.org/abs/2210.12036},
}
A set of segments in the plane may form a Euclidean TSP tour or a matching, among others. Optimal TSP tours as well as minimum weight perfect matchings have no crossing segments, but several heuristics and approximation algorithms may produce solutions with crossings. To improve such solutions, we can successively apply a flip operation that replaces a pair of crossing segments by non-crossing ones. This paper considers the maximum number D(n) of flips performed on n segments. First, we present reductions relating D(n) for different versions of matchings and the TSP tour. Second, we show that if all except t points are in convex position, then D(n) = O(tn2), providing a smooth transition between the convex O(n2) bound and the general O(n3) bound. Last, we show that if instead of counting the total number of flips, we only count the number of distinct flips, then the cubic upper bound improves to O(n8/3).
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SODA 2023, 1834-1861, 2023.
@inproceedings{coveringsconf,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
title = {Economical Convex Coverings and Applications},
pages = {1834--1861},
doi = {10.1137/1.9781611977554.ch70},
year = {2023},
url = {https://arxiv.org/abs/2303.08349},
}
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ε > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an $ε$ expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ε-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size nO(n) / ε(n-1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the Lp unit ball, this bound has been improved to 2O(n) / ε(n-1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. As an additional consequence, we obtain the fastest (1+ε)-approximate CVP algorithm that works in any norm, with a running time of 2O(n) / ε(n-1)/2 up to polynomial factors in the input size, and we obtain the fastest (1+ε)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of 2O(n)).
Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier; LATIN 2022, 730-745, 2022.
Extended abstract at EuroCG 2022 and ICALP 2022 Combinatorial Reconfiguration Workshop.
@inproceedings{untangleconf,
author = {Arun Kumar Das and Sandip Das and Guilherme D. da Fonseca and Yan Gerard and Bastien Rivier},
title = {Complexity Results on Untangling Red-Blue Matchings},
booktitle = {15th Latin American Theoretical Informatics Symposium (LATIN 2022)},
series = {Lecture Notes in Computer Science},
pages = {730--745},
year = {2022},
doi = {10.1007/978-3-031-20624-5_44},
url = {https://arxiv.org/abs/2202.11857},
}
Given a matching between n red points and n blue points by line segments in the plane, we consider the problem of obtaining a crossing-free matching through flip operations that replace two crossing segments by two non-crossing ones. We first show that (i) it is NP-hard to alpha-approximate the shortest flip sequence, for any constant alpha. Second, we show that when the red points are colinear, (ii) given a matching, a flip sequence of length at most n(n-1)/2 always exists, and (iii) the number of flips in any sequence never exceeds (n(n-1)/2) (n+4)/6. Finally, we present (iv) a lower bounding flip sequence with roughly 1.5 n(n-1)/2 flips, which shows that the n(n-1)/2 flips attained in the convex case are not the maximum, and (v) a convex matching from which any flip sequence has roughly 1.5 n flips. The last four results, based on novel analyses, improve the constants of state-of-the-art bounds.
Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; invited to SODA 2020 special issue of ACM Transactions on Algorithms, 18(4), 1-29, 2022.
@article{optcombcomp_journal,
author = {Arya, Rahul and Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
title = {Optimal Bound on the Combinatorial Complexity of Approximating Polytopes},
journal = {ACM Transactions on Algorithms},
pages = {1--29},
volume = {18},
number = {4},
doi = {10.1145/3559106},
url = {https://arxiv.org/abs/1910.14459},
year = {2022},
}
This paper considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) and an error parameter ε>0, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that O(1/ε(d-1)/2) facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this paper, we show that it is possible to construct a polytope with O(1/ε(d-1)/2) combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between ε-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are "essentially different." We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso; CG:SHOP 2021 special issue of ACM Journal of Experimental Algorithmics, 27, 3.2, 1-17, 2022.
The source code is available at github.com/gfonsecabr/shadoks-robots.
@article{CGSHOP21journal,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard and Aldo Gonzalez-Lorenzo and Pascal Lafourcade and Luc Libralesso},
journal = {ACM Journal of Experimental Algorithmics},
title = {Shadoks Approach to Low-Makespan Coordinated Motion Planning},
pages = {1--17},
volume = {27},
articleno = {3.2},
doi = {10.1145/3524133},
url = {https://arxiv.org/abs/2103.13956},
year = {2022},
}
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. It is a classical multi agent path finding problem with the specificity that the instances are highly dense in an unbounded grid. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them. The main ingredients include several different strategies to compute initial solutions coupled with a heuristic called Conflict Optimizer to reduce the makespan of existing solutions.
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo; invited as CG:SHOP paper of SoCG 2022, 71:1-8, 2022.
The source code is available at github.com/gfonsecabr/shadoks-CGSHOP2022.
@inproceedings{CGSHOP22conf,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard and Aldo Gonzalez-Lorenzo},
title = {Shadoks Approach to Minimum Partition into Plane Subgraphs},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
series = {LIPIcs},
volume = {},
pages = {71:1--71:8},
year = {2022},
doi = {10.4230/LIPIcs.SoCG.2022.71},
url = {},
}
We explain the heuristics used by the Shadoks team to win first place in the CG:SHOP 2022 challenge that considers the minimum partition into plane subgraphs. The goal is to partition a set of segments into as few subsets as possible such that segments in the same subset do not cross each other. The challenge has given 225 instances containing between 2500 and 75000 segments. For every instance, our solution was the best among all 32 participating teams.
Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard; CG:SHOP 2019 special issue of ACM Journal of Experimental Algorithmics, 27, 2.2, 1-11, 2022.
The source code is available at github.com/gfonsecabr/poLYG.
@article{CGSHOP19journal,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard},
journal = {ACM Journal of Experimental Algorithmics},
title = {Greedy and Local Search Heuristics to Build Area-Optimal Polygons},
pages = {1--11},
volume = {27},
articleno = {2.2},
doi = {10.1145/3503999},
year = {2022},
}
In this paper, we present our heuristic solutions to the problems of finding the maximum and minimum area polygons with a given set of vertices. Our solutions are based mostly on two simple algorithmic paradigms: greedy method and local search. The greedy heuristic starts with a simple polygon and adds vertices one by one, according to a weight function. A crucial ingredient to obtain good solutions is the choice of an appropriate weight function that avoids long edges. The local search part consists of moving consecutive vertices to another location in the polygonal chain. We also discuss the different implementation techniques that are necessary to reduce the running time.
Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso; invited as CG:SHOP paper of SoCG 2021, 63:1-9, 2021.
The source code is available at github.com/gfonsecabr/shadoks-robots.
@inproceedings{CGSHOP21conf,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard and Aldo Gonzalez-Lorenzo and Pascal Lafourcade and Luc Libralesso},
title = {Shadoks Approach to Low-Makespan Coordinated Motion Planning},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
series = {LIPIcs},
volume = {189},
pages = {63:1--63:9},
year = {2021},
doi = {10.4230/LIPIcs.SoCG.2021.63},
url = {https://arxiv.org/abs/2103.13956},
}
This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.
Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SODA 2020, 786-805, 2020.
@inproceedings{optcombcomp_conf,
author = {Arya, Rahul and Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)},
title = {Optimal Bound on the Combinatorial Complexity of Approximating Polytopes},
pages = {786--805},
doi = {10.1137/1.9781611975994.48},
url = {https://arxiv.org/abs/1910.14459},
year = {2020},
}
Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) along with an error parameter ε > 0. The objective is to determine a polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid-1970's, a result by Dudley showed that O(1/ε(d-1)/2) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices. While both results match known worst-case lower bounds, obtaining a corresponding upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a significant step forward towards this objective, obtaining a bound that is suboptimal by a factor of O(log(d-1)/2(1/eps)). In this paper, we improve this to an asymptotically optimal bound of O(1/ε(d-1)/2). Our result is based on a new relationship between ε-width caps of a convex body and its polar. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are "essentially different." We achieve our result by combining this with a variant of the witness-collector method and a novel variable-width layered construction.
Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard; FUN 2020, 11:1-15, 2020.
@inproceedings{battleship_conf,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard},
booktitle = {International Conference on Fun with Algorithms (FUN 2020)},
title = {Efficient Algorithms for {B}attleship},
pages = {11:1--15},
doi = {10.4230/LIPIcs.FUN.2021.11},
url = {https://arxiv.org/abs/2004.07354},
year = {2020},
}
We consider an algorithmic problem inspired by the battleship game. In the variant of the problem that we investigate, there is a unique ship of shape S which has been translated in the integer lattice. We assume that a player has already hit the ship with a first shot and the goal is to sink the ship using as few shots as possible, that is, by minimizing the number of missed shots. While the player knows the shape S, which position of S has been hit is not known. Given a shape S of n lattice points, the minimum number of misses that can be achieved in the worst case by any algorithm is called the battleship complexity of the shape S and denoted c(S). We prove three bounds on c(S), each considering a different class of shapes. First, we have c(S) ≤ n-1 for arbitrary shapes and the bound is tight for parallelogram-free shapes. Second, we provide an algorithm that shows that c(S) = O(log n) if S is an HV-convex polyomino. Third, we provide an algorithm that shows that c(S) = O(log log n) if S is a digital convex set. This last result is obtained through a novel discrete version of the Blaschke-Lebesgue inequality relating the area and the width of any convex body.
Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard; Journal of Mathematical Imaging and Vision (DGCI special issue), 62:693-703, 2020.
@article{digitalconvexityjournal,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard},
journal = {Journal of Mathematical Imaging and Vision},
title = {Efficient Algorithms to Test Digital Convexity},
pages = {693--703},
volume = {62},
doi = {10.1007/s10851-020-00957-6},
year = {2020},
}
A set S is digital convex if S is equal to the intersection of its convex hull and the set of lattice points. In this paper, we consider the following two problems. The first one is to test whether a given set S of n lattice points is digital convex. If the answer to the first problem is positive, then the second problem is to find a polygon P with minimum number of edges and whose intersection with the lattice is exactly S. We provide linear-time algorithms for these two problems. The algorithm is based on the well-known quickhull algorithm. The time to solve both problems is O(n + h log r) = O(n + n1/3 log r), where h = min(|conv(S)|, n1/3), conv(S) denotes the convex hull of S, and r is the diameter of S.
Gautam K. Das, Guilherme D. da Fonseca, and Ramesh K. Jallu; Discrete Applied Mathematics, 280:63-70, 2020.
@article{udg_is,
author = {Gautam K. Das and Guilherme D. da Fonseca and Ramesh K. Jallu},
title = {Efficient Independent Set Approximation in Unit Disk Graphs},
pages = {63--70},
volume = {280},
doi = {10.1016/j.dam.2018.05.049},
journal = {Discrete Applied Mathematics},
year = {2020},
}
We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing PTASs motivated the development of faster constant-approximation algorithms. In this article, we present a 2.16-approximation algorithm that runs in O(n log2 n) time and a 2-approximation algorithm that runs in O(n2 log n) time for the unweighted version of the problem. In the weighted versions, the running times increase by an O(log n) factor. Our algorithms are based on a classic strip decomposition, but we improve over previous algorithms by efficiently using geometric data structures. We also propose a polynomial-time approximation scheme for the unweighted version.
Ahmed Abdelkader, Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SODA 2019, 355-372, 2019.
@inproceedings{convexification_conf,
author = {Abdelkader, Ahmed and Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)},
title = {Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances},
pages = {355--372},
doi = {10.1137/1.9781611975482.23},
url = {https://arxiv.org/abs/2306.15621},
year = {2019},
}
We present a new approach to ε-approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We consider two families of distance functions: (a) convex scaling distance functions including the Mahalanobis distance, the Minkowski metric and multiplicative weights, and (b) Bregman divergences including the Kullback-Leibler divergence and the Itakura-Saito distance. As the fastest known data structures rely on the lifting transformation, their application is limited to the Euclidean metric, and alternative approaches for other distance functions are much less efficient. We circumvent the reliance on the lifting transformation by a careful application of convexification, which appears to be relatively new to computational geometry. We are given n points in d-dimensional space, each a site possibly defining its own distance function. Under mild assumptions on the growth rates of these functions, the proposed data structures answer queries in logarithmic time using O(n log(1/ε) / εd/2) space, which nearly matches the best known results for the Euclidean metric.
Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard; CCCG 2019, 124-132, 2019.
Extended abstract at EuroCG 2019, 19:1-7, 2019.
@inproceedings{digitalpotatoes,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard},
booktitle = {Canadian Conference in Computational Geometry (CCCG)},
title = {Peeling Digital Potatoes},
pages = {124--132},
url = {https://arxiv.org/abs/1812.05410},
year = {2019},
}
The potato-peeling problem (also known as convex skull) is a fundamental computational geometry problem and the fastest algorithm to date runs in O(n8) time for a polygon with n vertices that may have holes. In this paper, we consider a digital version of the problem. A set K is digital convex if K is equal to the intersection of its convex hull and the set of lattice points. Given a set S of n lattice points, we present polynomial time algorithms to the problems of finding the largest digital convex subset K of S (digital potato-peeling problem) and the largest union of two digital convex subsets of S. The two algorithms take roughly O(n3) and O(n9) time, respectively. We also show that those algorithms provide approximations to the continuous versions.
Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard; DGCI 2019, 409-419, 2019.
@inproceedings{digitalconvexity,
author = {Lo\"ic Crombez and Guilherme D. da Fonseca and Yan Gerard},
booktitle = {International Conference on Discrete Geometry for Computer Imagery (DGCI 2019)},
title = {Efficient Algorithms to Test Digital Convexity},
pages = {409--419},
doi = {10.1007/978-3-030-14085-4_32},
url = {https://arxiv.org/abs/1901.04738},
year = {2019},
}
A set S is digital convex if S is equal to the intersection of its convex hull and the set of lattice points. In this paper, we consider the algorithmic problem of testing whether a given set S of n lattice points is digital convex. Although convex hull computation requires Ω(n log n) time even for dimension d=2, we provide an algorithm for testing the digital convexity of S in O(n + h log r) time, where h is the number of edges of the convex hull and r is the diameter of S. This main result is obtained by proving that if S is digital convex, then the well-known quickhull algorithm computes the convex hull of S in linear time. In fixed dimension d, we present the first polynomial algorithm to test digital convexity, as well as a simpler and more practical algorithm whose running time may not be polynomial in n for certain inputs.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; ESA 2018, 3:1-14, 2018.
@inproceedings{minkowski_conf,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {European Symposium on Algorithms (ESA)},
title = {Approximate Convex Intersection Detection with Applications to Width and {M}inkowski Sums},
pages = {3:1--14},
doi = {10.4230/LIPIcs.ESA.2018.3},
url = {http://arxiv.org/abs/1807.00484},
year = {2018},
}
Approximation problems involving a single convex body in d-dimensional space have received a great deal of attention in the computational geometry community. In contrast, works involving multiple convex bodies are generally limited to dimensions d at most 3 and/or do not consider approximation. In this paper, we consider approximations to two natural problems involving multiple convex bodies: detecting whether two polytopes intersect and computing their Minkowski sum. Given an approximation parameter ε > 0, we show how to independently preprocess two polytopes A,B into data structures such that we can answer in polylogarithmic time if A and B intersect approximately. More generally, we can answer this for the images of A and B under affine transformations. Next, we show how to approximate the Minkowski sum of two given polytopes. Finally, we present a surprising impact of these results to a well studied problem that considers a single convex body. We show how to approximate the width of a set of n points in O(n log(1/ε) + 1/ε(d-1)/2 + α) time, for any constant α > 0, a major improvement over the previous bound.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SIAM Journal on Computing, 47(1):1-51, 2018.
@article{polytope_journal,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
title = {Approximate Polytope Membership Queries},
pages = {1--51},
doi = {10.1137/16M1061096},
journal = {SIAM Journal on Computing},
volume = {47},
number = {1},
url = {http://arxiv.org/abs/1604.01183},
year = {2018},
}
In the polytope membership problem, a convex polytope K in d-dimensional space is given, and the objective is to preprocess K into a data structure so that, given any query point q, it is possible to determine efficiently whether q is inside K. We consider this problem in an approximate setting. Given an approximation parameter ε, the query can be answered either way if the distance from q to K's boundary is at most ε times K's diameter. We assume that the dimension d is fixed, and K is presented as the intersection of n halfspaces. Previous solutions to approximate polytope membership were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former is optimal in the worst-case with respect to space, and the latter is optimal with respect to query time. We present four main results. First, we show how to combine the two above techniques to obtain a simple space-time trade-off. Second, we present an algorithm that dramatically improves this trade-off. We do not know whether the bounds of our algorithm are tight, but our third result shows a lower bound to the space achieved as a function of the query time. Our fourth result shows that it is possible to reduce approximate Euclidean nearest neighbor searching to approximate polytope membership queries. Combined with the above results, this provides significant improvements to the best known space-time trade-offs for approximate nearest neighbor searching.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SoCG 2017, 10:1-15, 2017.
Extended abstract at EuroCG 2017.
@inproceedings{kernel_socg,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {Symposium on Computational Geometry (SoCG 2017)},
title = {Near-Optimal $\varepsilon$-Kernel Construction and Related Problems},
pages = {10:1--15},
doi = {10.4230/LIPIcs.SoCG.2017.10},
url = {http://arxiv.org/abs/1703.10868},
year = {2017},
}
The computation of (i) ε-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In each case the input is a set of points in d dimensions for constant d and an approximation parameter ε > 0. In this paper, we describe new algorithms for these problems, achieving significant improvements to the exponent of the ε-dependency in their running times, from roughly d to d / 2 for the first two problems and from roughly d / 3 to d / 4 for problem (iii). These results are all based on an efficient decomposition of a convex body using a hierarchy of Macbeath regions, and contrast to previous solutions that decomposed the space using quadtrees and grids. By further application of these techniques, we also show that it is possible to obtain near-optimal preprocessing time for the most efficient data structures for (iv) approximate nearest neighbor searching, (v) directional width queries, and (vi) polytope membership queries.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; Discrete and Computational Geometry (SoCG special issue), 58(4):849-870, 2017.
@article{polytopecomp_dcg,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
title = {On the Combinatorial Complexity of Approximating Polytopes},
pages = {849--870},
doi = {10.1007/s00454-016-9856-5},
journal = {Discrete and Computational Geometry},
volume = {58},
number = {4},
year = {2017},
}
Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter diam(K) is given in Euclidean d-dimensional space, where d is a constant. Given an error parameter ε > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most ε diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/ε(d-1)/2) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is Õ(1/ε(d-1)/2), where Õ conceals a polylogarithmic factor in 1/ε. This is a significant improvement upon the best known bound, which is roughly O(1/εd-2). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Bárány and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SODA 2017, 270-288, 2017.
@inproceedings{membership,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)},
title = {Optimal Approximate Polytope Membership},
pages = {270--288},
doi = {10.1137/1.9781611974782.18},
year = {2017},
}
In the polytope membership problem, a convex polytope K in d-dimensional space is given, and the objective is to preprocess K into a data structure so that, given any query point q, it is possible to determine efficiently whether q is inside K. We consider this problem in an approximate setting, and assume that d is a constant. Given an approximation parameter ε, the query can be answered either way if the distance from q to K's boundary is at most ε times K's diameter. Previous solutions to the problem were in the form of a space-time trade-off, where logarithmic query time demands O(1/εd-1) storage, whereas storage O(1/ε(d-1)/2) admits roughly O(1/ε(d-1)/8) query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only O(1/ε(d-1)/2), which matches the worst-case lower bound on the complexity of any ε-approximating polytope. Our data structure is based on a completely new technique, a hierarchy of ellipsoids defined as approximations to Macbeath regions. As an application, we obtain major improvements to approximate nearest neighbor searching. Notably, the storage needed to answer ε-approximate nearest neighbor queries for a set of n points in logarithmic time is reduced to O(n/εd/2). This halves the exponent in the ε-dependency of the existing space bound of roughly O(n/εd), which has stood for 15 years (Har-Peled, 2001).
Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, and Celina M. H. de Figueiredo; International Journal of Computational Geometry and Applications, 27(4):255-276, 2017.
@article{intersec_linear,
author = {da Fonseca, Guilherme D. and de S\'{a}, Vin\'{i}cius G. P. and de Figueiredo, Celina M. H.},
title = {Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs},
journal = {International Journal of Computational Geometry and Applications},
doi = {10.1142/S0218195917500078},
pages = {255--276},
volume = {27},
number = {4},
year = {2017},
}
Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a variation of the known shifting strategy that allows us to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate the applicability of the proposed variation, we obtain results for three well-known optimization problems. Among such results, the proposed method yields linear-time (4+ε)-approximations for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing significant performance improvements when compared to previous algorithms that achieve the same approximation ratios. Finally, we use axis-aligned rectangles to illustrate that the same method may be used to derive linear-time approximations for problems on other geometric intersection graph classes.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SoCG 2016, 11:1-15, 2016.
@inproceedings{polytopecomp_socg,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {Symposium on Computational Geometry (SoCG 2016)},
title = {On the Combinatorial Complexity of Approximating Polytopes},
pages = {11:1--15},
doi = {10.4230/LIPIcs.SoCG.2016.11},
year = {2016},
}
Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter diam(K) is given in Euclidean d-dimensional space, where d is a constant. Given an error parameter ε > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most ε diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/ε(d-1)/2) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is Õ(1/ε(d-1)/2), where Õ conceals a polylogarithmic factor in 1/ε. This is a significant improvement upon the best known bound, which is roughly O(1/εd-2). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Bárány and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.
Emilio Vital Brazil, Celina M. H. de Figueiredo, Guilherme D. da Fonseca, and Diana Sasaki; Discrete Applied Mathematics, 210:112-122, 2016.
@article{perfection,
author = {Vital Brazil, Emilio and de Figueiredo, Celina M. H. and da Fonseca, Guilherme D. and Sasaki, Diana},
title = {The Cost of Perfection for Matchings in Graphs},
pages = {112--122},
doi = {doi:10.1016/j.dam.2014.12.006},
journal = {Discrete Applied Mathematics},
volume = {210},
year = {2016},
}
Perfect matchings and maximum weight matchings are two fundamental combinatorial structures. We consider the ratio between the maximum weight of a perfect matching and the maximum weight of a general matching. Motivated by the computer graphics application in triangle meshes, where we seek to convert a triangulation into a quadrangulation by merging pairs of adjacent triangles, we focus mainly on bridgeless cubic graphs. First, we characterize graphs that attain the extreme ratios. Second, we present a lower bound for all bridgeless cubic graphs. Third, we present upper bounds for subclasses of bridgeless cubic graphs, most of which are shown to be tight. Additionally, we present tight bounds for the class of regular bipartite graphs.
Guilherme D. da Fonseca, Bernard Ries, and Diana Sasaki; Discrete Applied Mathematics, 207:45-55, 2016.
@article{eta_grids,
author = {da Fonseca, Guilherme D. and Ries, Bernard and Sasaki, Diana},
title = {On the Ratio between Maximum Weight Perfect Matchings and Maximum Weight Matchings in Grids},
pages = {45--55},
doi = {10.1016/j.dam.2016.02.017},
journal = {Discrete Applied Mathematics},
volume = {207},
year = {2016},
}
Given a graph G that admits a perfect matching, we investigate the parameter η(G) (originally motivated by computer graphics applications) which is defined as follows. Among all nonnegative edge weight assignments, η(G) is the minimum ratio between (i) the maximum weight of a perfect matching and (ii) the maximum weight of a general matching. In this paper, we determine the exact value of η for all rectangular grids, all bipartite cylindrical grids, and all bipartite toroidal grids. We introduce several new techniques to this endeavor.
Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, and Celina M. H. de Figueiredo; WAOA 2014, Lecture Notes in Computer Science, 8952:132-143, 2015.
@inproceedings{udg_linear_conf,
author = {da Fonseca, Guilherme D. and de S\'{a}, Vin\'{i}cius G. P. and de Figueiredo, Celina M. H.},
booktitle = {Workshop on Approximation and Online Algorithms (WAOA 2014)},
title = {Linear-Time Approximation Algorithms for Unit Disk Graphs},
pages = {132--143},
doi = {10.1007/978-3-319-18263-6_12},
series = {Lecture Notes in Computer Science},
volume = {8952},
year = {2015},
}
Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approximation algorithms for unit disk graph problems. Our method yields linear-time (4+ε)-approximations to the maximum-weight independent set and the minimum dominating set, bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation factors. Furthermore, we present an alternative linear-time approximation scheme for the minimum vertex cover, which could be obtained by an indirect application of our method.
Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, Raphael Machado, and Celina M. H. de Figueiredo; Discrete Applied Mathematics, 197:3-19, 2015.
@article{udg_recog,
author = {da Fonseca, Guilherme D. and de S\'{a}, Vin\'{i}cius G. P. and Machado, Raphael and de Figueiredo, Celina M. H. },
title = {On the Recognition of Unit Disk Graphs and the Distance Geometry Problem with Ranges},
pages = {3--19},
doi = {10.1016/j.dam.2014.08.014},
journal = {Discrete Applied Mathematics},
volume = {197},
year = {2015},
}
We introduce a method to decide whether a graph G admits a realization on the plane in which two vertices lie within unitary distance from one another exactly if they are neighbors in G. Such graphs are called unit disk graphs, and their recognition is a known NP-hard problem. By iteratively discretizing the plane, we build a sequence of geometrically defined trigraphs–graphs with mandatory, forbidden and optional adjacencies–until either we find a realization of G or the interruption of such a sequence certifies that no realization exists. Additionally, we consider the proposed method in the scope of the more general Distance Geometry Problem with Ranges, where arbitrary intervals of pairwise distances are allowed.
Guilherme D. da Fonseca, Celina M. H. de Figueiredo, Vinícius G. Pereira de Sá, and Raphael Machado; Theoretical Computer Science, 540-541(26):70-81, 2014.
@article{domudg,
author = {da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and de S\'{a}, Vin\'{i}cius G. P. and Machado, Raphael},
title = {Efficient Sub-5 Approximations for Minimum Dominating Sets in Unit Disk Graphs},
pages = {70--81},
doi = {10.1016/j.tcs.2014.01.023},
journal = {Theoretical Computer Science},
volume = {540--541},
number = {26},
year = {2014},
}
A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc networks. Because the minimum dominating set problem for unit disk graphs is NP-hard, numerous approximation algorithms have been proposed in the literature, including some PTASs. However, since the proposal of a linear-time 5-approximation algorithm in 1995, the lack of efficient algorithms attaining better approximation factors has aroused attention. We introduce a linear-time O(n+m) approximation algorithm that takes the usual adjacency representation of the graph as input and outputs a 44/9-approximation. This approximation factor is also attained by a second algorithm, which takes the geometric representation of the graph as input and runs in O(n log n) time regardless of the number of edges. Additionally, we propose a 43/9-approximation which can be obtained in O(n2 m) time given only the graph's adjacency representation. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets.
Guilherme D. da Fonseca, Celina M. H. de Figueiredo, Vinícius G. Pereira de Sá, and Raphael Machado; WAOA 2012, Lecture Notes in Computer Science, 7846:82-92, 2013.
@inproceedings{domudg_conf,
author = {da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and de S\'{a}, Vin\'{i}cius G. P. and Machado, Raphael},
booktitle = {Workshop on Approximation and Online Algorithms (WAOA 2012)},
title = {Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs},
pages = {82--92},
doi = {10.1007/978-3-642-38016-7_8},
series = {Lecture Notes in Computer Science},
volume = {7846},
year = {2013},
}
A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc networks. Since the minimum dominating set problem for unit disk graphs is NP-hard, several approximation algorithms with different merits have been proposed in the literature. On one extreme, there is a linear time 5-approximation algorithm. On another extreme, there are two PTAS whose running times are polynomials of very high degree. We introduce a linear time approximation algorithm that takes the usual adjacency representation of the graph as input and attains a 44/9 approximation factor. This approximation factor is also attained by a second algorithm we present, which takes the geometric representation of the graph as input and runs in O(n log n) time, regardless of the number of edges. The analysis of the approximation factor of the algorithms, both of which are based on local improvements, exploits an assortment of results from discrete geometry to prove that certain graphs cannot be unit disk graphs. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SoCG 2012, 363-372, 2012.
@inproceedings{polytopeapx_socg,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {ACM Symposium on Computational Geometry (SoCG 2012)},
title = {Optimal Area-Sensitive Bounds for Polytope Approximation},
pages = {363--372},
doi = {10.1145/2261250.2261305},
url = {https://arxiv.org/abs/2306.15648},
year = {2012},
}
Approximating convex bodies is a fundamental question in geometry and has applications to a wide variety of optimization problems. Given a convex body K in Rd for fixed d, the objective is to minimize the number of vertices (alternatively, the number of facets) of an approximating polytope for a given Hausdorff error ε. The best known uniform bound, due to Dudley (1974), shows that O((diam(K)/ε)(d-1)/2) facets suffice. While this bound is optimal in the case of a Euclidean ball, it is far from optimal for skinny convex bodies. We show that, under the assumption that the width of the body in any direction is at least ε, it is possible to approximate a convex body using O((area(K)/εd-1)1/2) facets. This bound is never worse than the previous bound and may be significantly better for skinny bodies. This bound is provably optimal in the worst case and improves upon our earlier result (which appeared in SODA 2012). Our improved bound arises from a novel approach to sampling points on the boundary of a convex body in order to stab all (dual) caps of a given width. This approach involves the application of an elegant concept from the theory of convex bodies, called Macbeath regions. While Macbeath regions are defined in terms of volume considerations, we show that by applying them to both the original body and its dual, and then combining this with known bounds on the Mahler volume, it is possible to achieve the desired width-based sampling.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; SODA 2012, 29-42, 2012.
@inproceedings{mahler_soda,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)},
title = {Polytope Approximation and the Mahler Volume},
pages = {29--42},
doi = {10.1137/1.9781611973099.3},
year = {2012},
}
The problem of approximating convex bodies by polytopes is an important and well studied problem. Given a convex body K in Rd, the objective is to minimize the number of vertices (alternatively, the number of facets) of an approximating polytope for a given Hausdorff error ε. Dudley (1974) and Bronshteyn and Ivanov (1976) show that in spaces of fixed dimension, O((diam(K)/ε)(d-1)/2) vertices (alt., facets) suffice. In our first result, under the assumption that the width of the body is at least ε, we strengthen the above bound to Õ(√area(K)/ε(d-1)/2). This is never worse than the previous bound (by more than logarithmic factors) and may be significantly better for skinny bodies. Our analysis exploits an interesting analogy with a classical concept from the theory of convexity, called the Mahler volume. This is a dimensionless quantity that involves the product of the volumes of a convex body and its polar dual. In our second result, we apply the same machinery to improve upon the best known bounds for answering ε-approximate polytope membership queries. Given a convex polytope P defined as the intersection of halfspaces, such a query determines whether a query point q lies inside or outside P, but may return either answer if q's distance from P's boundary is at most ε. We show that, without increasing storage, it is possible to dramatically reduce the best known search times for ε-approximate polytope membership. This further implies improvements to the best known search times for approximate nearest neighbor searching in spaces of fixed dimension.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; STOC 2011, 579-586, 2011.
Extended abstract at EuroCG 2011.
@inproceedings{polytope_conf,
doi = {10.1145/1993636.1993713},
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {ACM Symposium on Theory of Computing (STOC 2011)},
title = {Approximate Polytope Membership Queries},
pages = {579--586},
year = {2011},
}
We consider an approximate version of a fundamental geometric search problem, polytope membership queries. Given a convex polytope P in Rd, presented as the intersection of halfspaces, the objective is to preprocess P so that, given a query point q, it is possible to determine efficiently whether q lies inside P subject to an allowed error ε. Previous solutions to this problem were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former yields minimum storage, the latter yields constant query time, and a space-time tradeoff can be obtained by interpolating between the two. We present the first significant improvements to this tradeoff. For example, using the same storage as Dudley, we reduce the query time from O(1/ε(d-1)/2) to O(1/ε(d-1)/4). Our approach is based on a very simple construction algorithm, whose analysis is surprisingly nontrivial. Both lower bounds and upper bounds on the performance of the algorithm are presented. To establish the relevance of our results, we introduce a reduction from approximate nearest neighbor searching to approximate polytope membership queries. Remarkably, we show that our tradeoff provides significant improvements to the best known space-time tradeoffs for approximate nearest neighbor searching. Furthermore, this is achieved with constructions that are much simpler than existing methods.
Guilherme D. da Fonseca; International Journal of Computational Geometry and Applications, 21(5):559-569, 2011.
Extended abstract at EuroCG 2010.
@article{flats,
author = {da Fonseca, Guilherme D.},
title = {Fitting Flats to Points with Outliers},
doi = {10.1142/S0218195911003809},
journal = {International Journal of Computational Geometry and Applications},
number = {5},
volume = {21},
pages = {559--569},
year = {2011},
}
Determining the best shape to fit a set of points is a fundamental problem in many areas of computer science. We present an algorithm to approximate the k-flat that best fits a set of n points with n - m outliers. This problem generalizes the smallest m-enclosing ball, infinite cylinder, and slab. Our algorithm gives an arbitrary constant factor approximation in O(nk+2/m) time, regardless of the dimension of the point set. While our upper bound nearly matches the lower bound, the algorithm may not be feasible for large values of k. Fortunately, for some practical sets of inliers, we reduce the running time to O(nk+2/mk+1), which is linear when m = Ω(n).
Vinícius G. Pereira de Sá, Celina M. H. de Figueiredo, Guilherme D. da Fonseca, and Raphael Machado; Theoretical Computer Science, 412(22):2370-2379, 2011.
@article{pgrid,
author = {de S\'{a}, Vin\'{i}cius G. P. and de Figueiredo, Celina M. H. and da Fonseca, Guilherme D. and Machado, Raphael},
doi = {10.1016/j.tcs.2011.01.018},
journal = {Theoretical Computer Science},
title = {Complexity Dichotomy on Partial Grid Recognition},
number = {22},
volume = {412},
pages = {2370--2379},
year = {2011},
}
Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a number of graph classes for which the problem is polynomial, even trivial. A natural step, outstanding thus far, was to provide a broad classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of allowed vertex degrees in the input graphs, yielding a full dichotomy on the complexity of the problem. As byproducts, the previous NP-completeness result for binary trees was strengthened to strictly binary trees, and the three-dimensional version of the problem was for the first time proven to be NP-complete. Our results were made possible by introducing the concepts of consistent orientations and robust gadgets, and by showing how the former allows NP-completeness proofs by local replacement even in the absence of the latter.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; ESA 2010, Lecture Notes in Computer Science, 6346:374-385, 2010.
@inproceedings{proximity,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {European Symposium on Algorithms (ESA 2010)},
series = {Lecture Notes in Computer Science},
volume = {6346},
pages = {374--385},
title = {A Unified Approach to Approximate Proximity Searching},
doi = {10.1007/978-3-642-15775-2_32},
year = {2010},
}
The inability to answer proximity queries efficiently for spaces of dimension d > 2 has led to the study of approximation to proximity problems. Several techniques have been proposed to address different approximate proximity problems. In this paper, we present a new and unified approach to proximity searching, which provides efficient solutions for several problems: spherical range queries, idempotent spherical range queries, spherical emptiness queries, and nearest neighbor queries. In contrast to previous data structures, our approach is simple and easy to analyze, providing a clear picture of how to exploit the particular characteristics of each of these problems. As applications of our approach, we provide simple and practical data structures that match the best previous results up to logarithmic factors, as well as advanced data structures that improve over the best previous results for all aforementioned proximity problems.
Vinícius G. Pereira de Sá, Celina M. H. de Figueiredo, Guilherme D. da Fonseca, and Raphael Machado; ISCO 2010, Electronic Notes in Discrete Mathematics, 36:391-398, 2010.
@inproceedings{vlsi_isco,
author = {de S\'{a}, Vin\'{i}cius G. P. and de Figueiredo, Celina M. H. and da Fonseca, Guilherme D. and Machado, Raphael},
booktitle = {International Symposium on Combinatorial Optimization},
series = {Electronic Notes in Discrete Mathematics},
title = {Complexity Dichotomy on Degree-Cconstrained VLSI Layouts with Unit-Length Edges},
volume = {36},
pages = {391--398},
doi = {10.1016/j.endm.2010.05.050},
year = {2010},
}
Deciding whether an arbitrary graph admits a VLSI layout with unit-length edges is NP-complete, even when restricted to binary trees. However, for certain graphs, the problem is polynomial or even trivial. A natural step, outstanding thus far, was to provide a broader classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of vertex degrees in the input graphs, yielding a comprehensive dichotomy on the complexity of the problem, with and without the restriction to trees.
Guilherme D. da Fonseca and David M. Mount; Computational Geometry: Theory and Applications (WADS special issue), 43(4):434-444, 2010.
@article{absolute,
author = {da Fonseca, Guilherme D. and Mount, David M.},
doi = {10.1016/j.comgeo.2008.09.009},
issn = {09257721},
journal = {Computational Geometry},
number = {4},
volume = {43},
pages = {434--444},
title = {Approximate range searching: The absolute model},
year = {2010},
}
Range searching is a well known problem in the area of geometric data structures. We consider this problem in the context of approximation, where an approximation parameter ε > 0 is provided. Most prior work on this problem has focused on the case of relative errors, where each range shape R is bounded, and points within distance ε diam(R) of the range's boundary may or may not be included. We consider a different approximation model, called the absolute model, in which points within distance ε of the range's boundary may or may not be included, regardless of the diameter of the range. We consider range spaces consisting of halfspaces, Euclidean balls, simplices, axis-aligned rectangles, and general convex bodies. We consider a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, and range emptiness. We show how idempotence can be used to improve not only approximate, but also exact halfspace range searching. Our data structures are much simpler than both their exact and relative model counterparts, and so are amenable to efficient implementation.
Celina M. H. de Figueiredo and Guilherme D. da Fonseca; Information Processing Letters, 109(21-22):1216-1221, 2009.
@article{enclosing,
author = {de Figueiredo, Celina M. H. and da Fonseca, Guilherme D.},
doi = {10.1016/j.ipl.2009.09.001},
issn = {00200190},
journal = {Information Processing Letters},
number = {21-22},
pages = {1216--1221},
title = {Enclosing weighted points with an almost-unit ball},
volume = {109},
year = {2009},
}
Given a set of n points with positive real weights in d-dimensional space, we consider an approximation to the problem of placing a unit ball, in order to maximize the sum of the weights of the points enclosed by the ball. Given an approximation parameter ε < 1, we present an O(n/εd-1) expected time algorithm that determines a ball of radius 1 + ε enclosing a weight at least as large as the weight of the optimal unit ball. This is the first approximate algorithm for the weighted version of the problem in d-dimensional space. We also present a matching lower bound for a certain class of algorithms for the problem.
Letícia R. Bueno, Luerbio Faria, Celina M. H. de Figueiredo, and Guilherme D. da Fonseca; Applicable Analysis and Discrete Mathematics, 3:386-394, 2009.
@article{odd,
author = {Bueno, Let\'{\i}cia R. and Faria, Luerbio and de Figueiredo, Celina M. H. and da Fonseca, Guilherme D.},
journal = {Applicable Analysis and Discrete Mathematics},
number = {2},
pages = {386--394},
title = {Hamiltonian Paths in Odd Graphs},
doi = {10.2298/AADM0902386B},
volume = {3},
year = {2009},
}
Lovász conjectured that every connected vertex-transitive graph has a Hamiltonian path. The odd graphs Ok form a well-studied family of connected, k-regular, vertex-transitive graphs. It was previously known that Ok has Hamiltonian paths for k ≤ 14. A direct computation of Hamiltonian paths in Ok is not feasible for large values of k, because Ok has binom(2k-1,k-1) vertices and kbinom(2k-1,k-1)/2 edges. We show that Ok has Hamiltonian paths for 15 ≤ k ≤ 18. We do so without running any heuristics. Instead, we use existing results on the middle levels problem, therefore relating these two fundamental problems. We show that further improved results for the middle levels problem can be used to find Hamiltonian paths in Ok for larger values of k.
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; in SIBGRAPI 2008, 237-244, 2008.
@inproceedings{tradeoffs-sibgrapi,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {21st Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI '08). },
doi = {10.1109/SIBGRAPI.2008.24},
pages = {237--244},
title = {Tradeoffs in Approximate Range Searching Made Simpler},
year = {2008},
}
Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in d-dimensional space into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter ε > 0 is given, and for a given query range R the points lying within distance ε diam(R) of the range's boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures.
Guilherme D. da Fonseca; in WADS 2007, Lecture Notes in Computer Science, 4619:2-14, 2007.
@inproceedings{absolute-wads,
author = {da Fonseca, Guilherme D.},
booktitle = {Algorithms and Data Structures (WADS 2007)},
chapter = {2},
doi = {10.1007/978-3-540-73951-7\_2},
issn = {0302-9743},
journal = {Algorithms and Data Structures},
pages = {2--14},
series = {Lecture Notes in Computer Science},
title = {Approximate Range Searching: The Absolute Model},
volume = {4619},
year = {2007},
}
Range searching is a well known problem in the area of geometric data structures. We consider this problem in the context of approximation, where an approximation parameter ε > 0 is provided. Most prior work on this problem has focused on the case of relative errors, where each range shape R is bounded, and points within distance ε diam(R) of the range's boundary may or may not be included. We consider a different approximation model, called the absolute model, in which points within distance ε of the range's boundary may or may not be included, regardless of the diameter of the range. We consider range spaces consisting of halfspaces, Euclidean balls, simplices, axis-aligned rectangles, and general convex bodies. We consider a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, and range emptiness. We show how idempotence can be used to improve not only approximate, but also exact halfspace range searching. Our data structures are much simpler than both their exact and relative model counterparts, and so are amenable to efficient implementation.
Celina M. H. de Figueiredo, Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, and Jeremy Spinrad; Algorithmica, 46(2):149-180, 2006.
@article{hssp,
author = {de Figueiredo, Celina M. H. and da Fonseca, Guilherme D. and de S\'{a}, Vinicius G. P. and Spinrad, Jeremy},
booktitle = {Algorithmica},
doi = {10.1007/s00453-005-1198-2},
issn = {0178-4617},
journal = {Algorithmica},
number = {2},
pages = {149--180},
title = {Algorithms for the Homogeneous Set Sandwich Problem},
volume = {46},
year = {2006},
}
A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs G1(V,E1), G2(V,E2), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph GS(V,ES), E1⊆ES⊆E2, which has a homogeneous set. In 2001, Tang et al. published an all-fast O(n2Δ2) algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset thereafter at former O(n4) determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic algorithms which have it established at O(n3 log m/n). We give as well two even faster O(n3) randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.
Celina M. H. de Figueiredo, Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, and Jeremy Spinrad; in WEA, Lecture Notes in Computer Science, 3058:243-252, 2004.
@inproceedings{hssp-wea,
author = {de Figueiredo, Celina M. and da Fonseca, Guilherme D. and de S\'{a}, Vin\'{\i}cius G. and Spinrad, Jeremy},
booktitle = {Experimental and Efficient Algorithms},
pages = {243--252},
title = {Faster Deterministic and Randomized Algorithms on the Homogeneous Set Sandwich Problem},
year = {2004}
}
A homogeneous set is a non-trivial, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs, G1(V,E1), G2(V,E2), we consider the problem of finding a sandwich graph GS(V,ES), with E1⊆ES⊆E2, which contains a homogeneous set, in case such a graph exists. This is called the Homogeneous Set Sandwich Problem (HSSP). We give an O(n3.5) deterministic algorithm, which updates the known upper bounds for this problem, and an O(n3) Monte Carlo algorithm as well. Both algorithms, which share the same underlying idea, are quite easy to be implemented on the computer.
Guilherme D. da Fonseca, Celina M. H. de Figueiredo, and Paulo C. P. Carvalho; Information Processing Letters, 89(3):151-157, 2004.
@article{hanger,
author = {da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P.},
doi = {10.1016/j.ipl.2003.10.010},
journal = {Information Processing Letters},
number = {3},
pages = {151--157},
title = {Kinetic hanger},
volume = {89},
year = {2004},
}
A kinetic priority queue is a kinetic data structure which determines the largest element in a collection of continuously changing numbers subject to insertions and deletions. Due to its importance, many different constructions have been suggested in the literature, each with its pros and cons. We propose a simple construction that takes advantage of randomization to achieve optimal locality and the same time complexity as most other efficient structures.
Vânia M. F. Dias, Guilherme D. da Fonseca, Celina M. H. de Figueiredo, and Jayme L. Szwarcfiter; Theoretical Computer Science, 306:391-405, 2003.
@article{sm_restricted,
author = {Dias, V\^{a}nia M. F. and da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Szwarcfiter, Jayme L.},
doi = {10.1016/S0304-3975(03)00319-0},
issn = {03043975},
journal = {Theoretical Computer Science},
number = {1-3},
pages = {391--405},
title = {The stable marriage problem with restricted pairs},
volume = {306},
year = {2003},
}
A stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. In an instance of the stable marriage problem, each of the n men and n women ranks the members of the opposite sex in order of preference. It is well known that at least one stable matching exists for every stable marriage problem instance. We consider extensions of the stable marriage problem obtained by forcing and by forbidding sets of pairs. We present a characterization for the existence of a solution for the stable marriage with forced and forbidden pairs problem. In addition, we describe a reduction of the stable marriage with forced and forbidden pairs problem to the stable marriage with forbidden pairs problem. Finally, we also present algorithms for finding a stable matching, all stable pairs and all stable matchings for this extension. The complexities of the proposed algorithms are the same as the best known algorithms for the unrestricted version of the problem.
Guilherme D. da Fonseca and Celina M. H. de Figueiredo; Information Processing Letters, 85(3):165-169, 2002.
@article{kinetic_heap,
author = {da Fonseca, Guilherme D. and de Figueiredo, Celina M. H.},
doi = {10.1016/S0020-0190(02)00366-6},
journal = {Information Processing Letters},
number = {3},
pages = {165--169},
title = {Kinetic heap-ordered trees: Tight analysis and improved algorithms},
volume = {85},
year = {2003},
}
The most natural kinetic data structure for maintaining the maximum of a collection of continuously changing numbers is the kinetic heap. Basch, Guibas, and Ramkumar proved that the maximum number of events processed by a kinetic heap with n numbers changing as linear functions of time is O(n log2 n) and Ω(n log n). We prove that this number is actually Θ(n log n). In the kinetic heap, a linear number of events are stored in a priority queue, consequently, it takes O(log n) time to determine the next event at each iteration. We also present a modified version of the kinetic heap that processes O(n log n / log log n) events, with the same O(log n) time complexity to determine the next event.
