Repositorio de producción científica de la Universidad de Sevilla

Covering point sets with two disjoint disks or squares

 

Búsqueda avanzada
 
Opened Access Covering point sets with two disjoint disks or squares
Citas

Estadísticas
Icon
Exportar a
Autor: Cabello, Sergio
Díaz Báñez, José Miguel
Seara Ojea, Carlos
Sellarés, J. Antoni
Urrutia, Jorge
Ventura Molina, Inmaculada
Departamento: Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI)
Fecha: 2007
Publicado en: Computational Geometry, 40 (3), 195-206.
Tipo de documento: Artículo
Resumen: We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks CR and CB with disjoint interiors such that the number of red points covered by CR plus the number of blue points covered by CB is maximized. We give an algorithm to solve this problem in O(n8/3 log2 n) time, where n denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares SR and SB instead of unit disks can be solved in O(nlog n) time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using O(n3 log n) time.
Cita: Cabello, S., Díaz Báñez, J.M., Seara, C., Sellarés, J.A., Urrutia, J. y Ventura Molina, I. (2007). Covering point sets with two disjoint disks or squares. Computational Geometry, 40 (3), 195-206.
Tamaño: 681.4Kb
Formato: PDF

URI: https://hdl.handle.net/11441/77941

DOI: 10.1016/j.comgeo.2007.10.001

Ver versión del editor

Salvo que se indique lo contrario, los contenidos de esta obra estan sujetos a la licencia de Creative Commons: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones