Guilherme Dias da Fonseca

I am now working at Unirio. This page is no longer up to date. Please go to http://www.uniriotec.br/~fonseca.

I was a Postdoc student in the department COPPE - Sistemas at UFRJ, Rio de Janeiro, Brazil from January 2008 to June 2009. My Postdoc advisor is Celina Figueiredo. You may also want to check my LATTES cv.

I got my PhD at University of Maryland, College Park in 2007. My PhD advisor was David Mount and the topic of my dissertation was approximate range searching in the absolute error model.

I'm specially interested in computational geometry, but I like anything related to algorithms (data structures, randomization, graphs, bioinformatics, complexity theory...). During my free time, I go rock climbing at places like Sugar Loaf.

Publications

• Enclosing Weighted Points with an Almost-Unit Ball; Celina M. H. de Figueiredo and Guilherme D. da Fonseca; Information Processing Letters, to appear, 2009.
  [ DOI ] [ PDF file ] [ QUICK ABSTRACT ]
• Hamiltonian Paths in Odd Graphs; Letícia R. Bueno, Luerbio Faria, Celina M. H. de Figueiredo, Guilherme D. da Fonseca; Applicable Analysis and Discrete Mathematics, 3, 386-394, 2009.
  [ DOI ] [ PDF file ] [ QUICK ABSTRACT ]
• Approximate Range Searching: The Absolute Model; Guilherme D. da Fonseca and David M. Mount; Computational Geometry: Theory and Applications, to appear, 2009.
  [ DOI ] [ PDF file ] [ QUICK ABSTRACT ]
• Tradeoffs in Approximate Range Searching Made Simpler; Sunil Arya, Guilherme D. da Fonseca, and David M. Mount; in SIBGRAPI 2008, 237-244, 2008.
  [ DOI ] [ PDF file ] [ QUICK ABSTRACT ]
• Approximate Range Searching: The Absolute Model; Guilherme D. da Fonseca; in WADS 2007, Lecture Notes in Computer Science vol 4619 pp 2-14, 2007.
  [ DOI ] [ PDF file ] [ PostScript file ] [ QUICK ABSTRACT ]
• Algorithms for the homogeneous set sandwich problem; Celina M. H. de Figueiredo, Guilherme D. da Fonseca, Vinícius G. P. de Sá, and Jeremy Spinrad; Algorithmica vol 46/2 pp 149-180, 2006.
  [ DOI ] [ PDF file ] [ PostScript file ] [ QUICK ABSTRACT ]
• Faster deterministic and randomized algorithms on the Homogeneous Set Sandwich Problem; Celina M. H. de Figueiredo, Guilherme D. da Fonseca, Vinícius G. P. de Sá, and Jeremy Spinrad; in III Workshop on Efficient and Experimental Algorithms (WEA2004), Lecture Notes in Computer Science vol 3058 pp 243 - 252, 2004.
  [ DOI ] [ PDF file ] [ PostScript file ] [ QUICK ABSTRACT ]
• Kinetic hanger; Guilherme D. da Fonseca, Celina M. H. de Figueiredo, and Paulo C. P. Carvalho; Information Processing Letters vol 89/3 pp 151 - 157, 2004.
  [ DOI ] [ PDF file ] [ PostScript file ] [ QUICK ABSTRACT ]
• Kinetic heap-ordered trees: tight analysis and faster algorithms; Guilherme D. da Fonseca and Celina M. H. de Figueiredo; Information Processing Letters vol 85/3 pp 165 - 169, 2002.
  [ DOI ] [ PDF file ] [ PostScript file ] [ QUICK ABSTRACT ]
• The stable marriage problem with restricted pairs; Vânia M. F. Dias, Guilherme D. da Fonseca, Celina M. H. de Figueiredo, and Jayme L. Szwarcfiter; Theoretical Computer Science vol 306 pp 391 - 405, 2003.
  [ DOI ] [ PostScript file ] [ QUICK ABSTRACT ]
• Stable marriages with restricted pairs (conference version); Vânia M. F. Dias, Guilherme D. da Fonseca, Celina M. H. de Figueiredo, and Jayme L. Szwarcfiter; in Brazilian Symposium on Graphs, Algorithms and Combinatorics, Electronic Notes in Discrete Mathematics vol 7, 2001.
[ DOI ]

Other Documents

• Tradeoffs in Approximate Range Searching Made Simpler. Slide presentation for SIBGRAPI 2008.
  [ OpenDocument Presentation ] [ Microsoft PPT file ] [ PDF file ]
• Approximate Range Searching in the Absolute Error Model. PhD dissertation.
  [ PDF file ]
• Approximate Range Searching in the Absolute Error Model. Slide presentation for the PhD defense.
  [ OpenDocument Presentation ] [ Microsoft PPT file ]
• Approximate Range Searching: The Absolute Model. Slide presentation for WADS 2007.
  [ OpenDocument Presentation ] [ PDF file ]

Documents in Portuguese

• Introdução aos Algoritmos Randomizados (Capítulo Geometria Computacional); Celina M. H. de Figueiredo, Manoel J. M. S. Lemos, Vinícius G. P. de Sá e Guilherme D. da Fonseca; 26° Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, 2007.
  [ Link ] [ PDF file ] [ PostScript file ]
• Apostila Introdutória de Algoritmos. Projeto desenvolvido em conjunto com Celina Figueiredo com bolsa FAPERJ em 2003.
  [ PDF file ]
• Listas de Prioridades Cinéticas. Tese de Mestrado, Engenharia de Sistemas e Computação, COPPE, UFRJ, 2003.
  [ PDF file ] [ PostScript file ]
• Listas de Prioridades Cinéticas. Apresentação da defesa de mestrado, 2003.
  [ OpenOffice Impress file ]
• Casamentos Estáveis com Casais Proibidos. Projeto final de graduação. Bacharelado em Ciência da Computação, UFRJ, 2000.
  [ PDF file ] [ Word DOC file ]

Teaching

• 2009/2: Geometria Computacional, with Claudio Esperança.
• 2009/1: Estruturas de Dados, with Jayme Szwarcfiter.
• Summer 2009: Aproximação Geométrica.
• 2008/3: Complexidade de Algoritmos, with Celina Figueiredo and Rafael Bernardo Teixeira.
• 2008/2: Geometria Computacional, with Celina Figueiredo.
• Fall 2007: Organization of Programming Languages, as a teaching TA for Atif Memon.
• Spring 2007: Computational Geometry, as a grading TA for David Mount.
• Fall 2006: Organization of Programming Languages, as a teaching TA for Marvin Zelkowitz.
• Summer 2006: Organization of Programming Languages, mentored by Larry Herman.
• Spring 2006: Organization of Programming Languages, as a teaching TA for Larry Herman.
• Fall 2005: Data Structures, as a grading TA for Michelle Hugue.
• Spring 2005: Data Structures, as a grading TA for Michelle Hugue.
• Fall 2004: Algorithms, as a grading TA for Clyde Kruskal.
• Spring 2004: Organization of Programming Languages, as a teaching TA for Larry Herman.
• Fall 2003: Organization of Programming Languages, as a teaching TA for Larry Herman.