I'm a computer science professor at Unirio, in Rio de Janeiro, Brazil. I was a Postdoc student at COPPE - UFRJ, advised by Celina Figueiredo. I got my PhD at the University of Maryland, College Park in 2007, advised by David Mount. Check my lattes cv for more details.
Eu sou professor de computação da Unirio, que fica na Praia Vermelha, na cidade do Rio de Janeiro. Fiz pós-doutorado na COPPE - UFRJ, sob orientação de Celina Figueiredo. Eu obtive meu doutorado na University of Maryland, College Park, em 2007, sob orientação de David Mount. Você pode encontrar mais informações no meu currículo lattes.
I'm especially interested in computational geometry, but I like working on anything related to algorithms (data structures, randomization, approximation, graphs, bioinformatics, complexity theory...). During my free time, I go rock climbing.
Meu principal interesse é geometria computacional, mas gosto de trabalhar com todos os assuntos relacionados a algoritmos (estruturas de dados, randomização, aproximação, grafos, bioinformática, teoria da complexidade...). Durante meu tempo livre, é provável que eu esteja escalando.
@inproceedings{proximity,
author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.},
booktitle = {European Symposium on Algorithms (ESA)},
series = {Lecture Notes in Computer Science},
title = {A Unified Approach to Approximate Proximity Searching},
url = {http://www.uniriotec.br/~fonseca/proximity.pdf},
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.
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).
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.
@inproceedings{flats_eurocg,
author = {da Fonseca, Guilherme D.},
booktitle = {EuroCG 2010},
title = {Fitting Flats to Points with Outliers},
pages = {169--172},
url = {http://www.uniriotec.br/~fonseca/flats_eurocg.pdf},
year = {2010}
}
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. For many practical sets of inliers, the running time is reduced to O(nk+2/mk+1), which is linear when m = Ω(n).
@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},
url = {http://www.uniriotec.br/~fonseca/vlsi_isco.pdf},
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.
@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},
url = {http://www.uniriotec.br/~fonseca/ARS-CGTA.pdf},
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.
@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},
url = {http://www.uniriotec.br/~fonseca/enclosing-IPL.pdf},
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.
@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},
url = {http://pefmath.etf.rs/accepted/819-Figueiredo-nv.pdf},
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 
vertices and k/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.
@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},
url = {http://www.uniriotec.br/~fonseca/tradeoffs-sibgrapi.pdf},
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.
@inproceedings{absolute-wads,
author = {da Fonseca, Guilherme D.},
booktitle = {Algorithms and Data Structures (WADS)},
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},
url = {http://www.uniriotec.br/~fonseca/ARS-WADS.pdf},
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.
@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},
url = {http://www.uniriotec.br/~fonseca/hssp-algorithmica.pdf},
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.
@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},
url = {http://www.uniriotec.br/~fonseca/hssp-mcd.pdf},
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.
@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},
issn = {00200190},
journal = {Information Processing Letters},
number = {3},
pages = {151--157},
title = {Kinetic hanger},
url = {http://www.uniriotec.br/~fonseca/hanger.pdf},
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.
@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},
url = {http://www.uniriotec.br/~fonseca/smtcs.ps},
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.
@article{kinetic_heap,
author = {da Fonseca, Guilherme D. and de Figueiredo, Celina M. H.},
doi = {10.1016/S0020-0190(02)00366-6},
issn = {00200190},
journal = {Information Processing Letters},
number = {3},
pages = {165--169},
title = {Kinetic heap-ordered trees: Tight analysis and improved algorithms},
url = {http://www.uniriotec.br/~fonseca/kh.pdf},
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.
