Publications

Reverse chronological order:

• E. Papadopoulou and M. Zavershynskyi. The higher-order Voronoi diagram of line segments. Algorithmica, to appear. Published online: December 2014, doi:10.1007/s00453-014-9950-0
• E. Khramtcova and E. Papadopoulou. Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures. Proc. 26th International Symposium on Algorithms and Computation (ISAAC), LNCS 9472, December 2015. (PDF)
  Short version in EuroCG 2015 (PDF)
• C. Bohler, P. Cheilaris, R. Klein, C.-H. Liu, E. Papadopoulou, and M. Zavershynskyi. On the complexity of higher order abstract Voronoi diagrams. Computational Geometry: Theory and Applications, 48(8):539--551, September 2015. doi:10.1016/j.comgeo.2015.04.008
• E. Papadopoulou and J. Xu. "The L_∞ Hausdorff Voronoi diagram revisited" International Journal of Computational Geometry and Applications, 25(2):123--141, 2015. (PDF)
• M. Claverol, E. Khramtcova, E. Papadopoulou, M. Saumell, and C. Seara. Stabbing circles for sets of segments in the plane. Abstracts XVI Spanish Meeting on Computational Geometry (XVI EGC), 2015.
• E. Khramtcova and E. Papadopoulou. Randomized incremental construction for the Hausdorff Voronoi diagram. Abstracts of Computational Geometry: Young Researchers Forum (CG:YRF), 2015.
• S. K. Dey, P. Cheilaris, N. Casati, M. Gabrani, and E. Papadopoulou. Topology and context-based pattern extraction using line-segment Voronoi diagrams. Proc. SPIE Advanced Lithography, Design-Process-Technology Co-optimization for Manufacturability IX, volume 9427, March 2015. Luigi Franco Cerrina Memorial Best Student Paper Award
• C.-H. Liu, E.Papadopoulou, and D. T. Lee. The k-Nearest-Neighbors Voronoi diagram revisited. Algorithmica, 71(2):429--449, February 2015.
• C. Bohler, C. H. Liu, E. Papadopoulou, and M. Zavershynskyi. A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams. Proc. 25th International Symposium on Algorithms and Computation (ISAAC), LNCS 8889, pages 27--37, December 2014.
• H. Bennett, E. Papadopoulou, and C. Yap. A subdivision approach to weighted Voronoi diagrams. Abstracts 24th Annual Fall Workshop on Computational Geometry, 2014.
• P. Cheilaris, S. K. Dey, M. Gabrani, and E. Papadopoulou. Implementing the L_∞ segment Voronoi diagram in CGAL and applying in VLSI pattern analysis. Proc. 4th International Congress on Mathematical software (ICMS), LNCS 8592, pages 198--205, 2014.
• P. Cheilaris, E. Khramtcova, S. Langerman, and E. Papadopoulou. A randomized incremental approach for the Hausdorff Voronoi diagram of non-crossing clusters. Proc. 11th Latin American Theoretical INformatics Symposium (LATIN), pages 96--107, March 2014.
• E. Khramtcova and E. Papadopoulou. A simple RIC for the Hausdorff Voronoi diagram of non-crossing clusters. Abstracts 30th European Workshop on Computational Geometry (EuroCG), 2014.
• G. Barequet and E. Papadopoulou. On farthest-site Voronoi diagrams of line segments and lines in three and higher dimensions. Abstracts 30th European Workshop on Computational Geometry (EuroCG), 2014.
• J. Xu, L. Xu, and E. Papadopoulou. Computing the map of geometric minimal cuts. Algorithmica, 68:805--834, 2014. doi:10.1007/s00453-012-9704-9 (PDF)
• E. Papadopoulou and S. K. Dey. On the farthest line-segment Voronoi diagram. International Journal of Computational Geometry and Applications, 23(6):443--459, 2013.
• E. Papadopoulou, J. Xu, and L. Xu. Map of geometric minimal cuts with applications. In P. M. Pardalos, D. Z. Du, and R. Graham, editors, Handbook of Combinatorial Optimization. Springer, 2nd edition, 2013.
• C. Bohler, P. Cheilaris, R. Klein, C.-H. Liu, E. Papadopoulou, and M. Zavershynskyi. On the complexity of higher order abstract Voronoi diagrams. Proc. 40th International Colloquium on Automata, Languages and Programming (ICALP), volume 7965 of LNCS, pages 208--219, July 2013.
• M. Zavershynskyi and E. Papadopoulou. A sweepline algorithm for higher order Voronoi diagrams. Proc. 10th International Symposium on Voronoi Diagrams in Science and Engineering, (ISVD), pages 16--22. IEEE-CS, July 2013.
  Short version in EuroCG 2013 (PDF)
• G. Barequet and E. Papadopoulou. On the farthest Voronoi diagram of line segments in three dimensions. Proc. 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), pages 31--36. IEEE-CS, July 2013.
• P. Cheilaris, E. Khramtcova, and E. Papadopoulou. Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters. Abstracts 29th European Workshop on Computational Geometry (EuroCG), pages 159--163, 2013.
• E. Papadopoulou, and M. Zavershynsky, "On higher-order Voronoi diagrams of line segments", 23rd International Symposium on Algorithms and Computation, ISAAC 2012, LNCS 7676, 177-186. (PDF)
  Short version in EuroCG 2012 (PDF)
• E. Papadopoulou, and S.K. Dey, "On the farthest line segment Voronoi diagram", 23rd International Symposium on Algorithms and Computation, ISAAC 2012, LNCS 7676, 187-196. (PDF)
  Short version in EuroCG 2012 (PDF)
• S.K. Dey and E. Papadopoulou, "The L_∞ (L_1;) farthest line segment Voronoi diagram", 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012, IEEE-CS, 49 - 55. 187-196. (PDF)
• E. Papadopoulou, "Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams", IEEE Trans. on Comp.-Aided Design, vol. 20, no.5, 583-597, May 2011. (PDF)
• E. Papadopoulou, and J. Xu, "The L_∞ Hausdorff Voronoi diagram revisited" , Proc. 8th Int. Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011, IEEE-CS, 67-74. (PDF)
  Shorter version in EuroCG 2011 (PDF)
• J. Xu, L. Xu, and E. Papadopoulou, "Computing the Map of Geometric Minimal Cuts" , Proc. 20th International Symposium on Algorithms and Computation, LNCS vol. 5878, 244-254, 2009.
• Puneet Gupta and Evanthia Papadopoulou, "Yield Analysis and Optimization", Chapter 7.3 in C.J. Alpert, D.P. Mehta, S.S. Sapatnekar editors, "The Handbook of Algorithms for VLSI Physical Design Automation", Taylor & Francis CRC Press, November 2008. (PDF)
• E. Papadopoulou, "The higher order Hausdorff Voronoi diagram and VLSI critical area extraction for via-blocks", Proc. 5th International Symposium on Voronoi Diagrams in Science and Engineering, September 2008, Kyiv Ukraine. (PDF)
• E. Papadopoulou, "Higher order Voronoi diagrams of segments for VLSI critical area extraction", Proc. 18th International Symposium on Algorithms and Computation, December 2007, Sendai, Japan, Lecture Notes in Computer Science 4835, 716-727. (PDF)
  Shorter version in 17th Fall Workshop on Computational and Combinatorial Geometry, IBM T.J. Watson Research Center, Hawthorn NY, November 2007. (PDF)
• E. Papadopoulou, "Net-aware critical area extraction for VLSI opens via Voronoi diagrams", 23rd European Workshop on Computational Geometry, Graz University of Technology, Austria, March 2007. (PDF)
• E. Papadopoulou"VLSI Critical Area Analysis via Voronoi Diagrams", article in "Innovation Matters" column of IBM Research, March 2006.
• Zhenming Chen, Evanthia Papadopoulou, Jinhui Xu, "Robustness of k-gon Voronoi diagram construction", Information Processing Letters, Vol. 97, no 4, 2006, 138-145. (PDF)
• Preliminary version in Proc. 14th Canadian Conference on Computational Geometry, University of Lethbridge, Lethbridge, Canada, August 2002.
• M. Mukherjee, S. Mansfield, Z. Zhao, L. Liebmann, M. Lavin, A. Lvov, E. Papadopoulou, "The problem of optimal placement of sub-resolution assist features (SRAFs)", Proc. SPIE--Optical Microlithography XVIII, SPIE'05, vol. 5754, 1417-1429. (PDF)
• Evanthia Papadopoulou, "The Hausdorff Voronoi diagram of point clusters in the plane", Algorithmica, 40, 2004, 63-82. (PDF)
• Preliminary version in Proc. Workshop on Algorithms and Data Structures, WADS 2003, Ottawa, Canada, Lecture Notes in Computer Science 2748, 439-450. (PDF)
• Evanthia Papadopoulou and D.T. Lee, "The Hausdorff Voronoi diagram of polygonal objects: a divide and conquer approach", International Journal of Computational Geometry and Applications, Vol. 14, No. 6, December 2004, 421-452. (PDF)
• Preliminary version: "The min-max Voronoi diagram of polygonal objects and applications in VLSI manufacturing", Proc. 13th International Symposium on Algorithms and Computation, November 2002, Vancouver, Canada, Lecture Notes in Computer Science 2518, 511-522. (PDF)
• Presented also at DIMACS Workshop on Computational Geometry, DIMACS Center, Rutgers University, Piscataway, NJ, November 2002.
• E. Papadopoulou, "Voronoi diagrams for VLSI manufacturing: robustness and implementation", DIMACS Workshop on Implementations of Geometric Algorithms, DIMACS Center, Rutgers University, Piscataway, NJ, Dec. 2002. (PDF)
• Evanthia Papadopoulou, "Critical Area computation for missing material defects in VLSI circuits", IEEE Transactions on Computer-Aided Design, vol. 20, no.5, May 2001, 583-597. (PDF)
• Preliminary version in Proc. International Symposium on Physical Design, San Diego, CA, April 2000, 140-146. (PDF)
• Early version presented at 4th CGC Workshop on Computational Geometry, Johns Hopkins University, Baltimore, MD, October 15-16, 1999.
• E. Papadopoulou and D.T. Lee, "The L_infinity Voronoi diagram of segments and VLSI applications", International Journal of Computational Geometry and Applications, Vol. 11, No. 5, 2001, 503-528. (PDF)
• Also presented at 6th SIAM Conference on Geometric Design, Albuquerque, New Mexico, November 2-5, 1999
• Evanthia Papadopoulou, "k-Pairs non-crossing shortest paths in a simple polygon", International Journal of Computational Geometry and Applications, vol. 9. No. 6, December 1999, 533-552. (PDF)
• Preliminary version in Proc. 7th Annual International Symposium on Algorithms and Computation, December 1996, Lecture Notes in Computer Science 1178, 305-314. (PDF)
• E. Papadopoulou and D.T. Lee, "Critical Area computation via Voronoi diagrams", IEEE Transactions on Computer-Aided Design, vol. 18, No. 4, April 1999, 463-474. (PDF)
• O. Aichholzer, F. Aurenhammer, D. Chen, D.T. Lee and E. Papadopoulou, "Skew Voronoi diagrams", International Journal of Computational Geometry and Applications, Vol. 9, No. 3, June 1999, 235-248. (PDF)
• Evanthia Papadopoulou, "L_infinity Voronoi diagrams and applications to VLSI layout and manufacturing", Proc. 9th International Symposium on Algorithms and Computation, December 1998, Taejon, Korea, Lecture Notes in Computer Science 1533, 9-18. (PDF)
• Presented also at 3rd CGC Workshop on Computational Geometry, Brown University, Providence, RI, October 11-12, 1998.
• E. Papadopoulou and D.T. Lee, "Critical area computation -- A new approach", Proc. International Symposium on Physical Design, Monterey, CA, April 1998, 89-94. (PDF)
• E. Papadopoulou and D.T. Lee, "A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains", Algorithmica, Vol. 20, No. 4, April 1998, 319-352. (PDF)
• Preliminary version in Proc. 3rd Annual European Symposium on Algorithms, September 1995. Lecture Notes in Computer Science 979, pp. 238-251. (PDF)
• O. Aichholzer, F. Aurenhammer, D. Chen, and D.T. Lee, A.Mukhopadhyay, and E. Papadopoulou, "Voronoi diagrams for direction--sensitive distances", Proc. 13th Annual ACM Symposium on Computational Geometry, Nice, France 1997, 418-420. (PDF)
• E. Papadopoulou and D.T. Lee, "The all-pairs quickest path problem", Information Processing Letters, April 1993, 45, 261-267. (PDF)
• E. Papadopoulou and D.T. Lee, "Shortest paths in a simple polygon in the presence of forbidden vertices", Proc. 6th Canadian Conference on Computational Geometry, August 1994, pp. 110-115. (PDF)