2 Search Results for "Karavelas, Menelaos"

Document
DOI: 10.4230/LIPIcs.SoCG.2016.33
Qualitative Symbolic Perturbation

Authors: Olivier Devillers, Menelaos Karavelas, and Monique Teillaud

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
In a classical Symbolic Perturbation scheme, degeneracies are handled by substituting some polynomials in epsilon for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach.
Cite as

Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. Qualitative Symbolic Perturbation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{devillers_et_al:LIPIcs.SoCG.2016.33,
  author =	{Devillers, Olivier and Karavelas, Menelaos and Teillaud, Monique},
  title =	{{Qualitative Symbolic Perturbation}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.33},
  URN =		{urn:nbn:de:0030-drops-59259},
  doi =		{10.4230/LIPIcs.SoCG.2016.33},
  annote =	{Keywords: Robustness issues, Symbolic perturbations, Apollonius diagram}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.81
A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes

Authors: Menelaos I. Karavelas and Eleni Tzanaki

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We derive tight expressions for the maximum number of k-faces, k=0,...,d-1, of the Minkowski sum, P_1+...+P_r, of r convex d-polytopes P_1,...,P_r in R^d, where d >= 2 and r < d, as a (recursively defined) function on the number of vertices of the polytopes. Our results coincide with those recently proved by Adiprasito and Sanyal [1]. In contrast to Adiprasito and Sanyal's approach, which uses tools from Combinatorial Commutative Algebra, our approach is purely geometric and uses basic notions such as f- and h-vector calculus, stellar subdivisions and shellings, and generalizes the methodology used in [10] and [9] for proving upper bounds on the f-vector of the Minkowski sum of two and three convex polytopes, respectively. The key idea behind our approach is to express the Minkowski sum P_1+...+P_r as a section of the Cayley polytope C of the summands; bounding the k-faces of P_1+...+P_r reduces to bounding the subset of the (k+r-1)-faces of C that contain vertices from each of the r polytopes. We end our paper with a sketch of an explicit construction that establishes the tightness of the upper bounds.
Cite as

Menelaos I. Karavelas and Eleni Tzanaki. A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 81-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{karavelas_et_al:LIPIcs.SOCG.2015.81,
  author =	{Karavelas, Menelaos I. and Tzanaki, Eleni},
  title =	{{A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{81--95},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.81},
  URN =		{urn:nbn:de:0030-drops-51428},
  doi =		{10.4230/LIPIcs.SOCG.2015.81},
  annote =	{Keywords: Convex polytopes, Minkowski sum, upper bound}
}
  • Refine by Author
  • 1 Devillers, Olivier
  • 1 Karavelas, Menelaos
  • 1 Karavelas, Menelaos I.
  • 1 Teillaud, Monique
  • 1 Tzanaki, Eleni

  • Refine by Classification

  • Refine by Keyword
  • 1 Apollonius diagram
  • 1 Convex polytopes
  • 1 Minkowski sum
  • 1 Robustness issues
  • 1 Symbolic perturbations
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2016

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 Imprint Privacy Contact