Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Abstract

We study a problem motivated by digital geometry: given a set of disjoint geometric regions, assign each region \(R_i\) a set of grid cells \(P_i\), so that \(P_i\) is connected, similar to \(R_i\), and does not touch any grid cell assigned to another region. Similarity is measured using the Hausdorff distance. We analyze the achievable Hausdorff distance in terms of the number of input regions, and prove asymptotically tight bounds for several classes of input regions.

Corresponding Publications

Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Ivor van der Hoog, Mees van der Kerkhof, Marc van Kreveld, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen

Proc. 2021 WADS Algorithms and Data Structures Symposium, 2021

Download Local Copy View Slides Export Citation 
@incollection{pixelpolygons2021,
  author = {van der Hoog, Ivor and van der Kerkhof, Mees and van Kreveld, Marc and
                 L{\"o}ffler, Maarten and Staals, Frank and Urhausen, J{\'e}r{\^o}me
                 and Vermeulen, Jordi L.},
  title = {Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance},
  booktitle = {Proc. 2021 WADS Algorithms and Data Structures Symposium},
  series = {LNCS},
  year = {2021},
  location = {Halifax, Canada (online)},
  publisher = {Springer},
  category = {other},
  pages = {627--640},
  doi = {10.1007/978-3-030-83508-8_45},
  url = {https://doi.org/10.1007/978-3-030-83508-8_45},
}

Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance

Ivor Hoog van der, Mees van der Kerkhof, Marc van Kreveld, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

Download Local Copy View Slides Export Citation 
@article{pixelpolygons_eurocg,
  author = {Hoog van der, Ivor and van der Kerkhof, Mees and van Kreveld, Marc and
                 L{\"o}ffler, Maarten and Staals, Frank and Urhausen, J{\'e}r{\^o}me
                 and Vermeulen, Jordi L.},
  title = {Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance},
  journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
  year = {2021},
  location = {St. Petersburg, Russia (online)},
  numpages = {7},
  category = {other},
  project = {pixelpolygons2021},
  url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_13.pdf},
}