Source author record

Christos Konaxis

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

ResearcherUnclaimed source record

Computational Geometry Symbolic Computation math.AG math.CO

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Sparse implicitization by interpolation: Geometric computations using matrix representations

Based on the computation of a superset of the implicit support, implicitization of a parametrically given hyper-surface is reduced to computing the nullspace of a numeric matrix. Our approach exploits the sparseness of the given parametric equations and of the implicit polynomial. In this work, we study how this interpolation matrix can be used to reduce some key geometric predicates on the hyper-surface to simple numerical operations on the matrix, namely membership and sidedness for given query points. We illustrate our results with examples based on our Maple implementation.

preprint2013arXiv

An Oracle-based, Output-sensitive Algorithm for Projections of Resultant Polytopes

We design an algorithm to compute the Newton polytope of the resultant, known as resultant polytope, or its orthogonal projection along a given direction. The resultant is fundamental in algebraic elimination, optimization, and geometric modeling. Our algorithm exactly computes vertex- and halfspace-representations of the polytope using an oracle producing resultant vertices in a given direction, thus avoiding walking on the polytope whose dimension is alpha-n-1, where the input consists of alpha points in Z^n. Our approach is output-sensitive as it makes one oracle call per vertex and facet. It extends to any polytope whose oracle-based definition is advantageous, such as the secondary and discriminant polytopes. Our publicly available implementation uses the experimental CGAL package triangulation. Our method computes 5-, 6- and 7-dimensional polytopes with 35K, 23K and 500 vertices, respectively, within 2hrs, and the Newton polytopes of many important surface equations encountered in geometric modeling in <1sec, whereas the corresponding secondary polytopes are intractable. It is faster than tropical geometry software up to dimension 5 or 6. Hashing determinantal predicates accelerates execution up to 100 times. One variant computes inner and outer approximations with, respectively, 90% and 105% of the true volume, up to 25 times faster.

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.

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.