Document Open Access Logo

Union of Hypercubes and 3D Minkowski Sums with Random Sizes

Authors Pankaj K. Agarwal, Haim Kaplan, Micha Sharir

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.10.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
  • Department of Computer Science, Duke University, Durham, NC 27708, USA
Haim Kaplan
  • School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Micha Sharir
  • School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Funding

  • Agarwal, Pankaj K.: Work on this paper by Pankaj Agarwal and Micha Sharir has been supported by Grant 2012/229 from the U.S.-Israel Binational Science Fund. Work by Pankaj Agarwal has also been supported by NSF under grants CCF-09-40671, CCF-10-12254, and CCF-11-61359, by ARO grants W911NF-07-1-0376 and W911NF-08-1-0452, and by an ERDC contract W9132V-11-C-0003.
  • Kaplan, Haim: Work by Haim Kaplan has been supported by grant 1841-14 from the Israel Science Fund, and grant 1367-2017 from the German-Israeli Science Fund.
  • Sharir, Micha: Work by Micha Sharir has also been supported by Grant 892-13 from the Israel Science Fund, by the Blavatnik Research Fund in Computer Science at Tel Aviv University, and by the Hermann Minkowski - MINERVA Center for Geometry at Tel Aviv University.

Cite As Get BibTex

Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Union of Hypercubes and 3D Minkowski Sums with Random Sizes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.10

Abstract

Let T={triangle_1,...,triangle_n} be a set of of n pairwise-disjoint triangles in R^3, and let B be a convex polytope in R^3 with a constant number of faces. For each i, let C_i = triangle_i oplus r_i B denote the Minkowski sum of triangle_i with a copy of B scaled by r_i>0. We show that if the scaling factors r_1, ..., r_n are chosen randomly then the expected complexity of the union of C_1, ..., C_n is O(n^{2+epsilon), for any epsilon > 0; the constant of proportionality depends on epsilon and the complexity of B. The worst-case bound can be Theta(n^3).
We also consider a special case of this problem in which T is a set of points in R^3 and B is a unit cube in R^3, i.e., each C_i is a cube of side-length 2r_i. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(n log^2 n), and it improves to O(n log n) if the scaling factors are chosen randomly from a "well-behaved" probability density function (pdf). We also extend the latter results to higher dimensions. For any fixed odd value of d, we show that the expected complexity of the union of the hypercubes is O(n^floor[d/2] log n) and the bound improves to O(n^floor[d/2]) if the scaling factors are chosen from a "well-behaved" pdf. The worst-case bounds are Theta(n^2) in R^3, and Theta(n^{ceil[d/2]}) in higher dimensions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Generating random combinatorial structures
Keywords
  • Computational geometry
  • Minkowski sums
  • Axis-parallel cubes
  • Union of geometric objects
  • Objects with random sizes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. K. Agarwal, A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararaman, and G. Zussman. The resilience of WDM networks to probabilistic geographical failures. IEEE/ACM Trans. on Netw., 21(5):1525-1538, 2013. Google Scholar
  2. P. K. Agarwal, S. Har-Peled, H. Kaplan, and M. Sharir. Union of random minkowski sums and network vulnerability analysis. Discrete Comput. Geom., 52(3):551-582, 2014. Google Scholar
  3. P.K. Agarwal and M. Sharir. Pipes, cigars, and kreplach: the union of minkowski sums in three dimensions. Discrete Comput. Geom., 24(4):645-657, Jan 2000. Google Scholar
  4. B. Aronov, A. Efrat, V. Koltun, and M. Sharir. On the union of κ-round objects in three and four dimensions. Discrete Comput. Geom., 36(4):511-526, 2006. Google Scholar
  5. B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air. Combinatorica, 10(2):137-173, 1990. Google Scholar
  6. B. Aronov and M. Sharir. Castles in the air revisited. Discrete Comput. Geom., 12(2):119-150, 1994. Google Scholar
  7. B. Aronov and M. Sharir. On translational motion planning of a convex polyhedron in 3-space. SIAM J. Comput., 26(6):1785-1803, 1997. Google Scholar
  8. B. Aronov, M. Sharir, and B. Tagansky. The union of convex polyhedra in three dimensions. SIAM J. Comput., 26(6):1670-1688, 1997. Google Scholar
  9. F. Aurenhammer, R. Klein, and D. T. Lee. Voronoi diagrams and Delaunay triangulations. World Scientific, 2013. Google Scholar
  10. J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom., 19(4):485-519, 1998. Google Scholar
  11. H.-C. Chang, S. Har-Peled, and B. Raichel. From proximity to utility: A voronoi partition of pareto optima. Discrete Comput. Geom., 56(3):631-656, 2016. Google Scholar
  12. E. Ezra. On the union of cylinders in three dimensions. Discrete Comput. Geom., 45(1):45-64, 2011. Google Scholar
  13. E. Ezra and M. Sharir. On the union of fat tetrahedra in three dimensions. J. ACM, 57(1):2:1-2:23, 2009. Google Scholar
  14. M. J. Golin and H.-S. Na. On the average complexity of 3d-voronoi diagrams of random points on convex polytopes. Comput. Geom: Theory Appls., 25(3):197-231, 2003. Google Scholar
  15. R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 1994. Google Scholar
  16. S. Har-Peled and B. Raichel. On the complexity of randomly weighted multiplicative voronoi diagrams. Discrete Comput. Geom., 53(3):547-568, 2015. Google Scholar
  17. J. Matoušek. Lectures on Discrete Geometry. Springer-Verlag, Berlin, Heidelberg, 2002. Google Scholar
  18. J. Pach P. K. Agarwal and M. Sharir. State of the union (of geometric objects). In J. Pach J. Goodman and R. Pollack, editors, Surveys on Discrete and Computational Geometry, pages 9-48. Amer. Math. Soc., Providence, RI, 2008. Google Scholar
  19. J. Pach, I. Safruti, and M. Sharir. The union of congruent cubes in three dimensions. Discrete Comput. Geom., 30(1):133-160, 2003. Google Scholar
  20. R. Schneider and J. A. Wieacker. Integral geometry. In P. M. Gruber and J. M. Wills, editors, Handbook of Convex Geometry, volume B, pages 1349-1390. North-Holland, Amsterdam, 1993. Google Scholar
  21. W. Weil and J. A. Wieacker. Stochastic geometry. In P. M. Gruber and J. M. Wills, editors, Handbook of Convex Geometry, volume B, pages 1393-1438. North-Holland, Amsterdam, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact