Voronoi diagram, Hausdorff Voronoi diagram, order-k Voronoi diagram, line segments, Euclidean distance, L-infinity metric, abstract Voronoi diagram
Barequet G., Papadopoulou E. (2014), On farthest-site Voronoi diagrams of line segments and lines in three and higher dimensions, in Abstracts of the 30th European Workshop on Computational Geometry (EuroCG)
, Ben-Gurion University of the Negev, Israel.
Khramtcova E., Papadopoulou E. (2014), A Simple RIC for the Hausdorff Voronoi Diagram of Non-crossing Clusters, in Abstracts of the 30th European Workshop on Computational Geometry (EuroCG)
, Ben-Gurion University , Israel.
Dey S. K., Cheilaris P., Casati N., Gabrani M., Papadopoulou E (2015), Topology and context-based pattern extraction using line-segment Voronoi diagrams, in SPIE Advanced Lithography, Design-Process-Technology Co-optimization for Man
, SPIE, SPIE digital library, Volume 9427.
Cheilaris P., Dey S. K., Gabrani M., Papadopoulou E. (2014), Implementing the L_ınfinity segment Voronoi diagram in CGAL and applying in VLSI pattern analysis, in 4th International Congress on Mathematical software (ICMS), LNCS
, Springer, Springer, LNCS 8592.
Khramtcova Elena, Papadopoulou Evanthia (2015), Randomized incremental construction for the Hausdorff Voronoi diagram, in Young Researchers Forum: Book of Abstracts, Computational Geometry Week, 2015
, Eindhoven, The NetherlandsAbstracts of Computational Geometry: Young Researchers Forum (CG:YRF)}, 2015, Eindhoven, Netherlands.
Khramtcova Elena, Papadopoulou Evanthia (2015), Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures
, University of Ljubljana, Ljubljana, Slovenia.
Cheilaris P., Khramtcova E., Langerman S., Papadopoulou E. (2016), A Randomized Incremental Approach for the Hausdorff Voronoi Diagram of Non-crossing Clusters, in Algorithmica
, 76(4), 935-960.
Dey S. K., Cheilaris P., Gabrani M., Papadopoulou E. (2016), Layout pattern analysis using the Voronoi diagram of line segments, in Journal of Micro/Nanolithography, MEMS, and MOEMS
, 15(1), 013504.
Claverol M., Khramtcova E., Papadopoulou E., Saumell M., Seara C. (2016), Stabbing circles for sets of segments in the plane, in 12th Latin American Theoretical INformatics Symposium (LATIN)
, Ensenada, MexicoSpringer, LNCS 9644, Springer.
Bennett H., Papadopoulou E., Yap C. (2014), A Subdivision Approach to Weighted Voronoi Diagrams
, University of Connecticut, http://fwcg14.cse.uconn.edu/program/.
Khramtcova Elena, Papadopoulou Evanthia (2015), Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures, in 26th International Symposium on Algorithms and Computation (ISAAC)
, Nagoya, JapanSpringer, LNCS, Springer.
Liu C.-H., Papadopoulou E., Lee D. T. (2015), The k-Nearest-Neighbor Voronoi diagram revisited, in Algorithmica
, 71(2), 429.
Bohler C., Cheilaris P., Klein R., Liu C.-H., Papadopoulou E., Zavershynskyi M. (2013), On the complexity of higher order abstract Voronoi diagrams, in 40th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 7965
, Springer, LNCS 7965, Springer.
Cheilaris Panagiotis, Khramtcova Elena, Papadopoulou Evanthia (2013), Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters, in 29th European Workshop on Computational Geometry (EuroCG)
, Braunschweig, GermanyTU Braunschweig, Braunschweig, Germany.
Barequet G., Papadopoulou E. (2013), On the farthest Voronoi diagram of line segments in three dimensions, in 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)
, St Petersburg, RussiaIEEE-CS, http://doi.ieeecomputersociety.org/10.1109/ISVD.2013.15.
Cheilaris Panagiotis, Khramtcova Elena, Langerman Stefan, Papadopoulou Evanthia (2014), A randomized incremental approach for the Hausdorff Voronoi diagram of non-crossing clusters, in LATIN 2014
, Springer, LNCS 8392, Springer.
Bohler C., Cheilaris P., Klein R., Liu C. H., Papadopoulou E., Zavershynskyi M. (2015), On the complexity of higher order abstract Voronoi diagrams, in Computational Geometry: Theory and Aplications
, 48(8), 539-551.
Khramtcova E., Papadopoulou E., Saumel M., Seara C. (accepted), Stabbing circles for sets of segments in the plane, in Abstracts of the XVI Spanish Meeting on Computational Geometry (XVI EGC)
, Barcelona, SpainUniversitat Polite`cnica de Catalunya, Spain, http://dccg.upc.edu/egc15/en/wp-content/uploads/2013/10/AbstractsXVIEGC.pdf.
This project will investigate fundamental open problems related to Hausdorff and higher-order Voronoi diagrams. The objective is to derive a deeper understanding of these basic structures, link them with the existing theoretical framework, and produce efficient but simple algorithms for their construction. Diverse application areas, such as the area of VLSI yield analysis and design manufacturability (DFM), can directly benefit from such algorithms. Specifically, we plan to investigate the following problems:
The Hausdorff Voronoi diagram of clusters of line-segments, more generally, the Hausdorff Voronoi diagram of clusters of polygonal objects, and abstract Hausdorff Voronoi diagrams. We will investigate different types of Hausdorff Voronoi diagrams, starting with the Hausdorff Voronoi diagram of clusters of line-segments. The Hausdorff Voronoi diagram of clusters of line segments is a natural generalization of the point cluster Hausdorff Voronoi diagram, which has been motivated by applications. In addition, we plan to investigate whether various Hausdorff Voronoi diagrams can be unified under a common abstract umbrella as ordinary Voronoi diagrams can. Abstract Voronoi diagrams are defined in terms of bisecting curves and they offer a unifying framework for many instances of concrete Voronoi diagrams.
Higher order Voronoi diagrams. We plan to explore the tight connection between Hausdorff Voronoi diagrams and higher-order Voronoi diagrams with the purpose of deriving simpler algorithms (e.g., plane sweep) to compute higher-order Voronoi diagrams even for the standard case of points, and expand the results to more general types of objects. Higher-order Voronoi diagrams are natural generalizations of the classic Voronoi diagram. In addition, we plan to explore the problem of unifying various concrete higher order Voronoi diagrams under the unifying concept of abstract Voronoi diagrams, in collaboration with CRP partner Rolf Klein.
Generalized Voronoi diagrams in simpler non-Euclidean (piecewise linear) metrics such as the L-infinity/ L-1 metrics. We plan to investigate possible simplifications in the structural complexity of generalized Voronoi diagrams in the L-infinity metric such as the farthest line segment Voronoi diagram, higher order Voronoi diagrams, and Hausdorff Voronoi diagrams. In addition, we plan to investigate software design and implementation issues for variants of L-infinity Voronoi diagrams. Ultimate goal (not explicitly included as a deliverable in this project) is the creation of open source code (CGAL based, http://www.cgal.org/) for the construction of different versions of generalized L-infinity Voronoi diagrams targeting VLSI applications.