Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 28
Encontrada(s) 1 página(s)

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Trajectory definition with high relative accuracy (HRA) by parametric representation of curves in nano-positioning systems

  • Díaz Pérez, Lucía
  • Rubio Serrano, Beatriz
  • Albajez García, José A.
  • Yagüe Fabra, José A.Y
  • Mainar Maza, Esmeralda
  • Torralba Gracia, Marta
Nanotechnology applications demand high accuracy positioning systems. Therefore, in order to achieve sub-micrometer accuracy, positioning uncertainty contributions must be minimized by implementing precision positioning control strategies. The positioning control system accuracy must be analyzed and optimized, especially when the system is required to follow a predefined trajectory. In this line of research, this work studies the contribution of the trajectory definition errors to the final positioning uncertainty of a large-range 2D nanopositioning stage. The curve trajectory is defined by curve fitting using two methods: traditional CAD/CAM systems and novel algorithms for accurate curve fitting. This novel method has an interest in computer-aided geometric design and approximation theory, and allows high relative accuracy (HRA) in the computation of the representations of parametric curves while minimizing the numerical errors. It is verified that the HRA method offers better positioning accuracy than commonly used CAD/CAM methods when defining a trajectory by curve fitting: When fitting a curve by interpolation with the HRA method, fewer data points are required to achieve the precision requirements. Similarly, when fitting a curve by a least-squares approximation, for the same set of given data points, the HRA method is capable of obtaining an accurate approximation curve with fewer control points.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Geometric properties and algorithms for rational q-Bézier curves and surfaces

  • Delgado, Jorge
  • Peña, J.M.
In this paper, properties and algorithms of q-Bézier curves and surfaces are analyzed. It is proven that the only q-Bézier and rational q-Bézier curves satisfying the boundary tangent property are the Bézier and rational Bézier curves, respectively. Evaluation algorithms formed by steps in barycentric form for rational q-Bézier curves and surfaces are provided.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Compensated evaluation of tensor product surfaces in CAGD

  • Delgado Gracia, J.
In computer-aided geometric design, a polynomial surface is usually represented in Bézier form. The usual form of evaluating such a surface is by using an extension of the de Casteljau algorithm. Using error-free transformations, a compensated version of this algorithm is presented, which improves the usual algorithm in terms of accuracy. A forward error analysis illustrating this fact is developed.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Maximum rectilinear convex subsets

  • González-Aguilar, H.
  • Orden, D.
  • Pérez-Lantero, P.
  • Rappaport, D.
  • Seara, C.
  • Tejel, J.
  • Urrutia, J.
Let P be a set of n points in the plane. We consider a variation of the classical Erdos-Szekeres problem, presenting efficient algorithms with (formula presented) running time and (formula presented) space complexity that compute: (1) A subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P, (2) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P and its interior contains no element of P, (3) a subset S of P such that the rectilinear convex hull of S has maximum area and its interior contains no element of P, and (4) when each point of P is assigned a weight, positive or negative, a subset S of P that maximizes the total weight of the points in the rectilinear convex hull of S.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Approximate trigonometric series expansions of some bounded solutions in the Tsien problem

  • Calvo, M.
  • Montijano, J.I.
  • Rández, L.
  • Elipe, A.
INTHE last decades, studies on the dynamics of a spacecraft that is moving in the gravitational field of a celestial body and subjected to some low-thrust propulsion system have attracted the attention of many researchers in astrodynamics. Here, we consider a particular case, the so-called Tsien problem [1], in which the spacecraft moves in a circular Keplerian orbit (often referred to as the parking orbit), and after a given time t0 0, it is subjected to a constant outward radial acceleration. By using the integrals of energy and angular momentum, this problem can be reduced to a two-dimensional scenario. Denoting by r and ? the polar coordinates that give the position of the spacecraft in the plane of the orbit [1], the differential equations that define their motion are ...
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Maximum rectilinear convex subsets

  • Gonzalez-Aguilar, H.
  • Orden, D.
  • Perez-Lantero, P.
  • Rappaport, D.
  • Seara, C.
  • Tejel, J.
  • Urrutia, J.
Let P be a set of n points in the plane. We consider a variation of the classical Erd\H os-Szekeres problem, presenting efficient algorithms with O(n3) running time and O(n2) space complexity that compute (1) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P, (2) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P and its interior contains no element of P, (3) a subset S of P such that the rectilinear convex hull of S has maximum area and its interior contains no element of P, and (4) when each point of P is assigned a weight, positive or negative, a subset S of P that maximizes the total weight of the points in the rectilinear convex hull of S. We also revisit the problems of computing a maximum area orthoconvex polygon and computing a maximum area staircase polygon, amidst a point set in a rectangular domain. We obtain new and simpler algorithms to solve both problems with the same complexity as in the state of the art.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Plane augmentation of plane graphs to meet parity constraints

  • Catana, J.C.
  • García, A.
  • Tejel, J.
  • Urrutia, J.
A plane topological graph G=(V, E) is a graph drawn in the plane whose vertices are points in the plane and whose edges are simple curves that do not intersect, except at their endpoints. Given a plane topological graph G=(V, E) and a set CG of parity constraints, in which every vertex has assigned a parity constraint on its degree, either even or odd, we say that G is topologically augmentable to meet CG if there exists a set E' of new edges, disjoint with E, such that G'=(V, E¿E') is noncrossing and meets all parity constraints. In this paper, we prove that the problem of deciding if a plane topological graph is topologically augmentable to meet parity constraints is NP-complete, even if the set of vertices that must change their parities is V or the set of vertices with odd degree. In particular, deciding if a plane topological graph can be augmented to a Eulerian plane topological graph is NP-complete. Analogous complexity results are obtained, when the augmentation must be done by a plane topological perfect matching between the vertices not meeting their parities. We extend these hardness results to planar graphs, when the augmented graph must be planar, and to plane geometric graphs (plane topological graphs whose edges are straight-line segments). In addition, when it is required that the augmentation is made by a plane geometric perfect matching between the vertices not meeting their parities, we also prove that this augmentation problem is NP-complete for plane geometric paths. For the particular family of maximal outerplane graphs, we characterize maximal outerplane graphs that are topological augmentable to satisfy a set of parity constraints. We also provide a polynomial time algorithm that decides if a maximal outerplane graph is topologically augmentable to meet parity constraints, and if so, produces a set of edges with minimum cardinality.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A decision tool based on bilevel optimization for the allocation of water resources in a hierarchical system

  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.
  • Mateo, Pedro M.
This paper addresses the optimal allocation of water among competing stakeholders during a finite planning horizon. We focus on those water systems where there are two levels of decision making organized according to a hierarchical framework. At the upper level, a central authority allocates water to demand points having regard to environmental and sustainability issues as well as balancing water users' supply/demand. At the lower level of the hierarchy, demand point managers allocate water to users prioritizing economic strategies. On the other hand, when it comes to allocating limited resources that affect public welfare, the authority in charge can also use different political instruments such as fees to influence the decisions made at those levels of decision making that are not directly within its competence. We propose a multiobjective multifollower bilevel optimization problem that aims to fulfill the central authority goals while including the reaction of the demand point managers in terms of optimization problems as constraints. Using the well-known Karush–Kuhn–Tucker approach, we transform the bilevel model into an equivalent multiobjective mixed-integer single-level model for which we provide tight big-M values. For the purpose of showing the versatility of the model, extensive computational experiments on a set of instances have been carried out. The results show that the optimization problem can be solved to optimality in small computing times using off-the-shelf mixed-integer solvers even for complex water systems and long planning periods. In addition, they illustrate the effect of imposing fees on the achievement of the central authority's objectives.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

On plane subgraphs of complete topological drawings

  • García Olaverri A.
  • Tejel Altarriba J.
  • Pilz A.
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dnof the complete graph Knon n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least [3n/2] edges. We also address the problem of obtaining a plane subgraph of Dnwith the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete. © 2021 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Rainbow polygons for colored point sets in the plane

  • Flores-Peñaloza D.
  • Kano M.
  • Martínez-Sandoval L.
  • Orden D.
  • Tejel J.
  • Tóth C.D.
  • Urrutia J.
  • Vogtenhuber B.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let rb-index(S) denote the smallest size of a perfect rainbow polygon for a colored point set S, and let rb-index(k) be the maximum of rb-index(S) over all k-colored point sets in general position; that is, every k-colored point set S has a perfect rainbow polygon with at most rb-index(k) vertices. In this paper, we determine the values of rb-index(k) up to k=7, which is the first case where rb-index(k)¿k, and we prove that for k=5, [Formula presented] Furthermore, for a k-colored set of n points in the plane in general position, a perfect rainbow polygon with at most [Formula presented] vertices can be computed in O(nlogn) time. © 2021 Elsevier B.V.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Inverse central ordering for the Newton interpolation formula

  • Carnicer, J. M.
  • Khiar, Y.
  • Peña, J. M.
An inverse central ordering of the nodes is proposed for the Newton interpolation formula. This ordering may improve the stability for certain distributions of nodes. For equidistant nodes, an upper bound of the conditioning is provided. This bound is close to the bound of the conditioning in the Lagrange interpolation formula, whose conditioning is the lowest. This ordering is related to a pivoting strategy of a matrix elimination procedure called Neville elimination. The results are illustrated with examples.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

  • Aichholzer, Oswin
  • García, Alfredo
  • Tejel, Javier
  • Vogtenhuber, Birgit
  • Weinberger, Alexandra
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once and there is a ray emanating from O which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((log n)/(log log n)). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate computations with Wronskian matrices

  • Mainar, E.
  • Peña, J.M.
  • Rubio, B.
In this paper we provide algorithms for computing the bidiagonal decomposition of the Wronskian matrices of the monomial basis of polynomials and of the basis of exponential polynomials. It is also shown that these algorithms can be used to perform accurately some algebraic computations with these Wronskian matrices, such as the calculation of their inverses, their eigenvalues or their singular values and the solutions of some linear systems. Numerical experiments illustrate the results.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

The school bus routing problem with student choice: a bilevel approach and a simple and effective metaheuristic

  • Calvete, H.I.
  • Galé, C.
  • Iranzo, J.A.
  • Toth, P.
The school bus routing problem (SBRP) involves interrelated decisions such as selecting the bus stops, allocating the students to the selected bus stops, and designing the routes for transporting the students to the school taking into account the bus capacity constraint, with the objective of minimizing the cost of the routes. This paper addresses the SBRP when the reaction of students to the selection of bus stops is taken into account, that is, when students are allowed to choose the selected bus stop that best suits them. A bilevel optimization model with multiple followers is formulated, and its transformation into a single-level mixed integer linear programming (MILP) model is proposed. A simple and effective metaheuristic algorithm is also developed to solve the problem. This algorithm involves solving four MILP problems at the beginning, which can be used to obtain tight upper bounds of the optimal solution. Extensive computational experiments on SBRP benchmark instances from the literature show the effectiveness of the proposed algorithm in terms of both the quality of the solution found and the required computing time.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Spherical Bessel functions and critical lengths

  • Carnicer, J. M.
  • Mainar, E.
  • Peña, J. M.
The critical length of a space of functions can be described as the supremum of the length of the intervals where Hermite interpolation problems are unisolvent for any choice of nodes. We analyze the critical length for spaces containing products of algebraic polynomials and trigonometric functions. We show the relation of these spaces with spherical Bessel functions and bound above their critical length by the first positive zero of a Bessel function of the first kind.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Bidiagonal decompositions of Vandermonde-type matrices of arbitrary rank

  • Delgado, Jorge
  • Koev, Plamen
  • Marco, Ana
  • Martínez, José-Javier
  • Peña, Juan Manuel
  • Persson, Per-Olof
  • Spasov, Steven
We present a method to derive new explicit expressions for bidiagonal decompositions of Vandermonde and related matrices such as the (-, -) Bernstein-Vandermonde ones, among others. These results generalize the existing expressions for nonsingular matrices to matrices of arbitrary rank. For totally nonnegative matrices of the above classes, the new decompositions can be computed efficiently and to high relative accuracy componentwise in floating point arithmetic. In turn, matrix computations (e.g., eigenvalue computation) can also be performed efficiently and to high relative accuracy.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate bidiagonal decomposition of collocation matrices of weighted ¿-transformed systems

  • Mainar, Esmeralda
  • Peña, Juan Manuel
  • Rubio, Beatriz
Given a system of functions, we introduce the concept of weighted f-transformed system, which will include a very large class of useful representations in Statistics and Computer Aided Geometric Design. An accurate bidiagonal decomposition of the collocation matrices of these systems is obtained. This decomposition is used to present computational methods with high relative accuracy for solving algebraic problems with collocation matrices of weighted f-transformed systems such as the computation of eigenvalues, singular values, and the solution of some linear systems. Numerical examples illustrate the accuracy of the performed computations.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Twisted ways to find plane structures in simple drawings of complete graphs

  • Aichholzer, Oswin
  • García, Alfredo
  • Tejel, Javier
  • Vogtenhuber, Birgit
  • Weinberger, Alexandra
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains [fórmula] pairwise disjoint edges and a plane cycle (and hence path) of length [fórmula]. Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Stabilized recovery and model reduction for multivariate exponential polynomials

  • Peña, Juan Manuel
  • Sauer, Tomas
Recovery of multivariate exponential polynomials, i.e., the multivariate version of Prony's problem, can be stabilized by using more than the minimally needed multiinteger samples of the function. We present an algorithm that takes into account this extra information and prove a backward error estimate for the algebraic recovery method SMILE. In addition, we give a method to approximate data by an exponential polynomial sequence of a given structure as a step in the direction of multivariate model reduction.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate Algorithms for Bessel Matrices

  • Delgado, Jorge
  • Orera, Héctor
  • Peña, J.M.
In this paper, we prove that any collocation matrix of Bessel polynomials at positive points is strictly totally positive, that is, all its minors are positive. Moreover, an accurate method to construct the bidiagonal factorization of these matrices is obtained and used to compute with high relative accuracy the eigenvalues, singular values and inverses. Similar results for the collocation matrices for the reverse Bessel polynomials are also obtained. Numerical examples illustrating the theoretical results are included. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate bidiagonal decomposition and computations with generalized Pascal matrices

  • Delgado, J.
  • Orera, H.
  • Peña, J.M.
This paper provides an accurate method to obtain the bidiagonal factorization of many generalized Pascal matrices, which in turn can be used to compute with high relative accuracy the eigenvalues, singular values and inverses of these matrices. Numerical examples are included.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Optimal properties of tensor product of B-bases

  • Delgado Gracia, J
  • Orera, H
  • Peña Ferrández, JM
It is proved the optimal conditioning for the infinity-norm of collocation matrices of the tensor product of normalized B-bases among the tensor product of all normalized totally positive bases of the corresponding space of functions. Bounds for the minimal eigenvalue and singular value and illustrative numerical examples are also included. (C) 2021 Elsevier Ltd. All rights reserved.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

High relative accuracy with matrices of q-integers

  • Delgado J.
  • Orera H.
  • Peña J.M.
This article shows that the bidiagonal decomposition of many important matrices of q-integers can be constructed to high relative accuracy (HRA). This fact can be used to compute with HRA the eigenvalues, singular values, and inverses of these matrices. These results can be applied to collocation matrices of q-Laguerre polynomials, q-Pascal matrices, and matrices formed by q-Stirling numbers. Numerical examples illustrate the theoretical results. © 2021 John Wiley & Sons Ltd.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Error bounds for linear complementarity problems of BpR -matrices

  • Orera, H.
  • Peña, J.M.
It is proved that any BpR-matrix has positive determinant. For p> 0 , norm bounds for the inverses of BpR-matrices and error bounds for linear complementarity problems associated with BpR-matrices are provided. In this last case, the bounds are simpler than previous bounds and also have the advantage that they can be used without previously knowing whether we have a BpR-matrix. Some numerical examples show that these new bounds can be considerably sharper than previous ones.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Radon’s construction and matrix relations generating syzygies

  • Carnicer, J. M.
  • Godés, C.
  • Sauer, T.
Let ¿n be the set of bivariate polynomials of degree not greater than n. A ¿n-correct set of nodes is a set such that the Lagrange interpolation problem with respect to these nodes has a unique solution. A maximal line of a ¿n-correct set is any line containing exactly n+ 1 nodes. Syzygy matrices can be used to find linear factors of the fundamental polynomials and detect maximal lines. We suggest to use matrix relations in order to generate syzygies, identify linear factors of fundamental polynomials and detect maximal lines. We interpret our results in the important case of GC sets trying to shed some light on the Gasca-Maeztu conjecture.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Characterizations and accurate computations for tridiagonal Toeplitz matrices

  • Delgado, J.
  • Orera, H.
  • Peña, J.M.
Tridiagonal Toeplitz P-matrices, M-matrices and totally positive matrices are characterized. For some classes of tridiagonal matrices and tridiagonal Toeplitz matrices, it is shown that many algebraic computations can be performed with high relative accuracy.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

High relative accuracy with some special matrices related to G and ß functions

  • Delgado, Jorge
  • Peña, Juan Manuel
For some families of totally positive matrices using Γ and functions, we provide their bidiagonal factorization. Moreover, when these functions are define dover integers, we prove that the bidiagonal factorization can be computed with high relative accuracy and so we can compute with high relative accuracy their eigenvalues,singular values,inverses and the solutions of some associated linear systems. We provide numerical examples illustrating this high relative accuracy.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A matheuristic for solving the bilevel approach of the facility location problem with cardinality constraints and preferences

  • Calvete, H.I.
  • Galé, C.
  • Iranzo, J.A.
  • Camacho-Vallejo, J.F.
  • Casas-Ramírez, M.S.
This paper addresses a generalized version of the facility location problem with customer preferences which includes an additional constraint on the number of customers which can be allocated to each facility. The model aims to minimize the total cost due to opening facilities and allocating customers while taking into account both customer preferences for the facilities and these cardinality constraints. First, two approaches to deal with this problem are proposed, which extend the single level and bilevel formulations of the problem in which customers are free to select their most preferred open facility. After analyzing the implications of assuming any of the two approaches, in this research, we adopt the approach based on the hierarchical character of the model which leads to the formulation of a bilevel optimization problem. Then, taking advantage of the characteristics of the lower level problem, a single level reformulation of the bilevel optimization model is developed based on duality theory which does not require the inclusion of additional binary variables. Finally, we develop a simple but effective matheuristic for solving the bilevel optimization problem whose general framework follows that of an evolutionary algorithm and exploits the bilevel structure of the model. The chromosome encoding pays attention to the upper level variables and controls the facilities which are open. Then, an optimization model is solved to allocate customers in accordance with their preferences and the availability of the open facilities. A computational experiment shows the effectiveness of the matheuristic in terms of the quality of the solutions yielded and the computing time.