Source author record

Menelaos I. Karavelas

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry math.CO

Catalog footprint

Research overview

7works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

We derive tight expressions for the maximum number of $k$ -faces, $0\le{}k\le{}d-1$ , of the Minkowski sum, $P_1+...+P_r$ , of $r$ convex $d$ -polytopes $P_1,...,P_r$ in $\mathbb{R}^d$ , where $d\ge{}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 [2]. 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 and shellings, and generalizes the methodology used in [15] and [14] 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 $\mathcal{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 $\mathcal{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.

preprint2012arXiv

The maximum number of faces of the Minkowski sum of three convex polytopes

We derive tight expressions for the maximum number of $k$ -faces, $0\le k\le d-1$ , of the Minkowski sum, $P_1+P_2+P_3$ , of three $d$ -dimensional convex polytopes $P_1$ , $P_2$ and $P_3$ , as a function of the number of vertices of the polytopes, for any $d\ge 2$ . Expressing the Minkowski sum of the three polytopes as a section of their Cayley polytope $\mathcal{C}$ , the problem of counting the number of $k$ -faces of $P_1+P_2+P_3$ , reduces to counting the number of $(k+2)$ -faces of the subset of $\mathcal{C}$ comprising of the faces that contain at least one vertex from each $P_i$ . In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of $r$ $d$ -polytopes, where $r\ge d$ . For $d\ge 4$ , the maximum values are attained when $P_1$ , $P_2$ and $P_3$ are $d$ -polytopes, whose vertex sets are chosen appropriately from three distinct $d$ -dimensional moment-like curves.

preprint2011arXiv

Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments

In this paper we study the most-demanding predicate for computing the Euclidean Voronoi diagram of axes-aligned line segments, namely the Incircle predicate. Our contribution is two-fold: firstly, we describe, in algorithmic terms, how to compute the Incircle predicate for axes-aligned line segments, and secondly we compute its algebraic degree. Our primary aim is to minimize the algebraic degree, while, at the same time, taking into account the amount of operations needed to compute our predicate of interest. In our predicate analysis we show that the Incircle predicate can be answered by evaluating the signs of algebraic expressions of degree at most 6; this is half the algebraic degree we get when we evaluate the Incircle predicate using the current state-of-the-art approach. In the most demanding cases of our predicate evaluation, we reduce the problem of answering the Incircle predicate to the problem of computing the sign of the value of a linear polynomial (in one variable), when evaluated at a known specific root of a quadratic polynomial (again in one variable). Another important aspect of our approach is that, from a geometric point of view, we answer the most difficult case of the predicate via implicitly performing point locations on an appropriately defined subdivision of the place induced by the Voronoi circle implicated in the Incircle predicate.

preprint2011arXiv

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

Given a set $Σ$ of spheres in $\mathbb{E}^d$ , with $d\ge{}3$ and $d$ odd, having a fixed number of $m$ distinct radii $ρ_1,ρ_2,...,ρ_m$ , we show that the worst-case combinatorial complexity of the convex hull $CH_d(Σ)$ of $Σ$ is $Θ(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$ , where $n_i$ is the number of spheres in $Σ$ with radius $ρ_i$ . To prove the lower bound, we construct a set of $Θ(n_1+n_2)$ spheres in $\mathbb{E}^d$ , with $d\ge{}3$ odd, where $n_i$ spheres have radius $ρ_i$ , $i=1,2$ , and $ρ_2\neρ_1$ , such that their convex hull has combinatorial complexity $Ω(n_1n_2^{\lfloor\frac{d}{2}\rfloor}+n_2n_1^{\lfloor\frac{d}{2}\rfloor})$ . Our construction is then generalized to the case where the spheres have $m\ge{}3$ distinct radii. For the upper bound, we reduce the sphere convex hull problem to the problem of computing the worst-case combinatorial complexity of the convex hull of a set of $m$ $d$ -dimensional convex polytopes lying on $m$ parallel hyperplanes in $\mathbb{E}^{d+1}$ , where $d\ge{}3$ odd, a problem which is of independent interest. More precisely, we show that the worst-case combinatorial complexity of the convex hull of a set $\{\mathcal{P}_1,\mathcal{P}_2,...,\mathcal{P}_m\}$ of $m$ $d$ -dimensional convex polytopes lying on $m$ parallel hyperplanes of $\mathbb{E}^{d+1}$ is $O(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$ , where $n_i$ is the number of vertices of $\mathcal{P}_i$ . We end with algorithmic considerations, and we show how our tight bounds for the parallel polytope convex hull problem, yield tight bounds on the combinatorial complexity of the Minkowski sum of two convex polytopes in $\mathbb{E}^d$ .

preprint2011arXiv

The maximum number of faces of the Minkowski sum of two convex polytopes

We derive tight expressions for the maximum number of $k$ -faces, $0\le{}k\le{}d-1$ , of the Minkowski sum, $P_1\oplus{}P_2$ , of two $d$ -dimensional convex polytopes $P_1$ and $P_2$ , as a function of the number of vertices of the polytopes. For even dimensions $d\ge{}2$ , the maximum values are attained when $P_1$ and $P_2$ are cyclic $d$ -polytopes with disjoint vertex sets. For odd dimensions $d\ge{}3$ , the maximum values are attained when $P_1$ and $P_2$ are $\lfloor\frac{d}{2}\rfloor$ -neighborly $d$ -polytopes, whose vertex sets are chosen appropriately from two distinct $d$ -dimensional moment-like curves.

preprint2011arXiv

Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick

Consider a set of $r$ convex $d$ -polytopes $P_1,P_2,...,P_r$ , where $d\ge{}3$ and $r\ge{}2$ , and let $n_i$ be the number of vertices of $P_i$ , $1\le{}i\le{}r$ . It has been shown by Fukuda and Weibel that the number of $k$ -faces of the Minkowski sum, $P_1+P_2+...+P_r$ , is bounded from above by $Φ_{k+r}(n_1,n_2,...,n_r)$ , where $Φ_{\ell}(n_1,n_2,...,n_r)= \sum_{\substack{1\le{}s_i\le{}n_i s_1+...+s_r=\ell}} \prod_{i=1}^r\binom{n_i}{s_i}$ , $\ell\ge{}r$ . Fukuda and Weibel have also shown that the upper bound mentioned above is tight for $d\ge{}4$ , $2\le{}r\le{}\lfloor\frac{d}{2}\rfloor$ , and for all $0\le{}k\le{}\lfloor\frac{d}{2}\rfloor-r$ . In this paper we construct a set of $r$ neighborly $d$ -polytopes $P_1,P_2,...,P_r$ , where $d\ge{}3$ and $2\le{}r\le{}d-1$ , for which the upper bound of Fukuda and Weibel is attained for all $0\le{}k\le{}\lfloor\frac{d+r-1}{2}\rfloor-r$ . Our approach is based on what is known as the Cayley trick for Minkowski sums. A direct consequence of our result is a tight asymptotic bound on the complexity of the Minkowski sum $P_1+P_2+...+P_r$ , for any fixed dimension $d$ and any $2\le{}r\le{}d-1$ , when the number of vertices of the polytopes is (asymptotically) the same.

preprint2010arXiv

Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs

We consider the problem of monitoring an art gallery modeled as a polygon, the edges of which are arcs of curves, with edge or mobile guards. Our focus is on piecewise-convex polygons, i.e., polygons that are locally convex, except possibly at the vertices, and their edges are convex arcs. We transform the problem of monitoring a piecewise-convex polygon to the problem of 2-dominating a properly defined triangulation graph with edges or diagonals, where 2-dominance requires that every triangle in the triangulation graph has at least two of its vertices in its 2-dominating set. We show that $\lfloor\frac{n+1}{3}\rfloor$ diagonal guards or $\lfloor\frac{2n+1}{5}\rfloor$ edge guards are always sufficient and sometimes necessary, in order to 2-dominate a triangulation graph. Furthermore, we show how to compute: a diagonal 2-dominating set of size $\lfloor\frac{n+1}{3}\rfloor$ in linear time, an edge 2-dominating set of size $\lfloor\frac{2n+1}{5}\rfloor$ in $O(n^2)$ time, and an edge 2-dominating set of size $\lfloor\frac{3n}{7}\rfloor$ in O(n) time. Based on the above-mentioned results, we prove that, for piecewise-convex polygons, we can compute: a mobile guard set of size $\lfloor\frac{n+1}{3}\rfloor$ in $O(n\log{}n)$ time, an edge guard set of size $\lfloor\frac{2n+1}{5}\rfloor$ in $O(n^2)$ time, and an edge guard set of size $\lfloor\frac{3n}{7}\rfloor$ in $O(n\log{}n)$ time. Finally, we show that $\lfloor\frac{n}{3}\rfloor$ mobile or $\lceil\frac{n}{3}\rceil$ edge guards are sometimes necessary. When restricting our attention to monotone piecewise-convex polygons, the bounds mentioned above drop: $\lceil\frac{n+1}{4}\rceil$ edge or mobile guards are always sufficient and sometimes necessary; such an edge or mobile guard set, of size at most $\lceil\frac{n+1}{4}\rceil$ , can be computed in O(n) time.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Menelaos I. Karavelas

Research overview

Is this your work?

7 publications

A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

The maximum number of faces of the Minkowski sum of three convex polytopes

Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

The maximum number of faces of the Minkowski sum of two convex polytopes

Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick

Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs

See the researcher in context

Building this map preview