Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Draining a polygon-or-rolling a ball out of a polygon

Autor
Aloupis, G.; Cardinal, J.; Collete, S.; Hurtado, F.; Langerman, S.; O'Rourke, J.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2014-02
Volum
47
Número
2, Part C
Pàgina inicial
316
Pàgina final
328
DOI
https://doi.org/10.1016/j.comgeo.2009.08.002 Obrir en finestra nova
Resum
We introduce the problem of draining water (or balls representing water drops) out of a punctured polygon (or a polyhedron) by rotating the shape. For 2D polygons, we obtain combinatorial bounds on the number of holes needed, both for arbitrary polygons and for special classes of polygons. We detail an O(n(2) log n) algorithm that finds the minimum number of holes needed for a given polygon, and argue that the complexity remains polynomial for polyhedra in 3D. We make a start at characterizing t...
Paraules clau
Draining, Injection-filling, Polygons, Polyhedral molds
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Aloupis, Greg  (autor)
  • Cardinal, Jean  (autor)
  • Collete, Sebastien  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Langerman, Stefan  (autor)
  • O'Rourke, Joseph  (autor)