Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/12090

Computing similarity between piecewise-linear functions
Agarwal, Pankaj; Aronov, Boris; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
We study the problem of computing the similarity between two piecewise-linear bivariate functions de ned over a common domain, where the surfaces they de ne in 3D|polyhedral terrains|can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4=3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1+")-approximation algorithm for minimizing the area that runs in O(n=p") time, for any xed " > 0. The (1 + ")- approximation algorithm for the bivariate version, where volume is minimized, runs in O(n="2) time, for any xed " > 0, provided the two functions are de ned over the same triangulation of their domain.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Programació matemàtica
Geometric programming
Programació geomètrica
Classificació INSPEC::Optimisation::Mathematical programming::Geometric programming
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/submittedVersion
info:eu-repo/semantics/conferenceObject
ACM Press. Association for Computing Machinery
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Agarwal, Pankaj; Aronov, Boris; Van Kreveld, Matias; Löffler, Maarten; Silveira, Rodrigo Ignacio
Speckmann, Bettina; Silveira, Rodrigo Ignacio; Aronov, Boris; Buchin, Kevin; Buchin, Maike; Jansen, Bart; De Jong, Tom; Kreveld, Marc van; Loffler, Maarten; Luo, Jun
Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Luo, Jun; Silveira, Rodrigo Ignacio
Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio; Wenk, Carola; Wiratma, Lionov
Buchin, Kevin; Kostitsyna, Irina; Löffler, Maarten; Silveira, Rodrigo Ignacio