Elias' Article

Minkowski decomposition of convex lattice polygons.
Ioannis Z. Emiris and Elias P. Tsigaridas.
In M. Elkadi, B. Mourrain, and R. Piene, editors, Algebraic geometry and geometric modeling, pp. 207–224, Springer, 2005.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 220.5kB  [gzipped postscript] 281.3kB  

Abstract:

A relatively recent area of study in geometric modelling concerns toric Bézier patches. In this line of work, several questions reduce to testing whether a given convex lattice polygon can be decomposed into a Minkowski sum of two such polygons and, if so, to finding one or all such decompositions. Other motivations for this problem include sparse resultant computation, especially for the implicitization of parametric surfaces, and factorization of bivariate polynomials. % Particularly relevant for geometric modelling are decompositions where at least one summand has a small number of edges. We study the complexity of Minkowski decomposition and propose efficient algorithms for the case of constant-size summands. We have implemented these algorithms and illustrate them by various experiments with random lattice polygons and on all convex lattice polygons with zero or one interior lattice points. % We also express the general problem by means of standard and well-studied problems in combinatorial optimization. This leads to an improvement in asymptotic complexity and, eventually, to efficient randomized algorithms and implementations.

@InCollection{et-aggm-2005,
  author =       {Ioannis~Z. Emiris and Elias~P. Tsigaridas},
  title =        {Minkowski decomposition of convex lattice polygons},
  editor =       {M. Elkadi and B. Mourrain and R. Piene},
  booktitle =    {Algebraic geometry and geometric modeling},
  publisher =    "Springer",
  year =         2005,
  pages =        "207--224",
  abstract =     "A relatively recent area of study in geometric
                  modelling concerns toric B\'ezier patches.  In this
                  line of work, several questions reduce to testing
                  whether a given convex lattice polygon can be
                  decomposed into a Minkowski sum of two such polygons
                  and, if so, to finding one or all such
                  decompositions.  Other motivations for this problem
                  include sparse resultant computation, especially for
                  the implicitization of parametric surfaces, and
                  factorization of bivariate polynomials.  %
                  Particularly relevant for geometric modelling are
                  decompositions where at least one summand has a
                  small number of edges.  We study the complexity of
                  Minkowski decomposition and propose efficient
                  algorithms for the case of constant-size summands.
                  We have implemented these algorithms and illustrate
                  them by various experiments with random lattice
                  polygons and on all convex lattice polygons with
                  zero or one interior lattice points.  % We also
                  express the general problem by means of standard and
                  well-studied problems in combinatorial optimization.
                  This leads to an improvement in asymptotic
                  complexity and, eventually, to efficient randomized
                  algorithms and implementations.",
}

Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02