Artículo
Constrained many-to-many point matching in two dimensions
Autor/es | Caraballo de la Cruz, Luis Evaristo
Castro Campos, Rodrigo Alexander Díaz Báñez, José Miguel Heredia Velasco, Marco Antonio Urrutia Galicia, Jorge Ventura Molina, Inmaculada Zaragoza Martínez, Francisco Javier |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) |
Fecha de publicación | 2024-01-26 |
Fecha de depósito | 2024-02-27 |
Publicado en |
|
Resumen | In the minimum-weight many-to-many point matching problem, we are given a set R of red points and a set B of blue points in the plane, of total size N, and we want to pair up each point in R to one or more points in B and ... In the minimum-weight many-to-many point matching problem, we are given a set R of red points and a set B of blue points in the plane, of total size N, and we want to pair up each point in R to one or more points in B and vice versa so that the sum of distances between the paired points is minimized. This problem can be solved in O(N3) time by using a reduction to the minimum-weight perfect matching problem, and thus, it is not fast enough to be used for on-line systems where a large number of tunes need to be compared. Motivated by similarity problems in music theory, in this paper we study several constrained minimum-weight many-to-many point matching problems in which the allowed pairings are given by geometric restrictions, i.e., a bichromatic pair can be matched if and only if the corresponding points satisfy a specific condition of closeness. We provide algorithms to solve these constrained versions in O(N) time when the sets R and B are given ordered by abscissa. |
Agencias financiadoras | European Union (UE). H2020 Ministerio de Ciencia e Innovación (MICIN). España Universidad Autónoma de México (UNAM) |
Identificador del proyecto | CIN/AEI/10.13039/501100011033
PID2020-114154RB-I00 PAPIIT IN105221 |
Cita | Caraballo de la Cruz, L.E., Castro Campos, R.A., Díaz Báñez, J.M., Heredia Velasco, M.A., Urrutia Galicia, J., Ventura Molina, I. y Zaragoza Martínez, F.J. (2024). Constrained many-to-many point matching in two dimensions. Optimization Letters. https://doi.org/10.1007/s11590-023-02089-3. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Constrained many-to-many point ... | 1.256Mb | [PDF] | Ver/ | |