suma de mikouski

Una operación entre polígonos: Sumas de Minkowski
María Teresa Taranilla (1)
Gustavo Kavka

Edilma Olinda Gagliardi
(1)

(2)

Departamento de Informática
(2)

Gregorio Hernández Peñalver

(1)

Departamento de Matemática Aplicada

LIDIC♦

Facultad de Ciencias Físico, Matemáticas y Naturales

Facultad de Informática

Universidad Nacional de San Luis, Argentina

UniversidadPolitécnica de Madrid, España

{ tarani, gkavka, oli }@unsl.edu.ar

gregorio@fi.upm.es

Fax: 54-2652-430224

Fax: 34-91-3367426

Resumen:
Dados dos conjuntos P y Q ⊂ R2, la suma de Minkowski de P y Q, denotada por
P ⊕ Q se define como P ⊕ Q = { p + q : p ∈ P, q ∈Q }.
Las sumas de Minkowski son utilizadas en un amplio rango de aplicaciones, tales
como planificación de movimientos derobots, procesamiento de imágenes, sistemas de
información geográfica, marcado y corte de moldes, entre otras.
En este trabajo se presentan las Sumas de Minkowski, mostrando aspectos
teóricos, sus posibles aplicaciones, se describen los algoritmos que las calculan y
finalmente, se introduce una herramienta para el cálculo de sumas de Minkowski entre
polígonos.

Palabras claves: Sumas deMinkowski, Geometría Computacional.

♦

Laboratorio de Investigación y Desarrollo en Inteligencia Computacional. Director: Dr. Raúl H. Gallard.
Este artículo es parcialmente suvencionado por el Proyecto Al2002-1010-2.43 Geometría Computacional, de la
Universidad Politécnica de Madrid, España.

1. Introducción
La Geometría Computacional es una disciplina que brinda un marco teórico y formalpara el
diseño de estructuras y análisis de algoritmos requeridos para dar soluciones a problemas que
surgen en las más diversas áreas de la Informática. Actualmente ha cobrado un gran interés debido a
las numerosas aplicaciones que tiene en distintas áreas de investigación [Abe00], [BKOS97]
[Tou85], [Tou92].
La Geometría Computacional se ocupa de resolver problemas geométricos de modoconstructivo. El volumen de datos que se maneja en muchas aplicaciones suele ser muy elevado,
por lo que es necesario buscar una solución basada en dos parámetros que midan la complejidad de
un algoritmo: el espacio y el tiempo[AHU74].
En este trabajo se hace hincapié en un tema particular de la Geometría que son las sumas de
Minkowski. Las sumas de Minkowski son utilizadas en un amplio rango deaplicaciones, tales como
planificación de movimientos de robots [Lat91], procesamiento de imágenes [Ser82], [Ser88],
sistemas de información geográfica [HCC98], marcado y corte de moldes[Li94], entre otras.
Uno de los objetivos de nuestro trabajo, fue introducirnos en el estudio e investigación de las
sumas de Minkowski, su contexto teórico, aplicaciones más destacadas y realizar un estudio quemuestre el estado del arte del tema presentando los aspectos teóricos y prácticos más relevantes
[GTBH02] [BS01], [AFH01].
Otro de los objetivos planteados, fue desarrollar una herramienta que implemente la suma de
Minkowski entre distintos tipos de polígonos, tanto entre polígonos convexos y no convexos, que
pueda ser utilizada como una herramienta de trabajo, de simulación y de apoyo en laenseñanza de
la Geometría Computacional [KT02].
En el presente artículo, introducimos el concepto de sumas de Minkowski y describimos
algunas de sus aplicaciones más relevantes. Luego, presentamos los algoritmos que permiten
realizar el cálculo de la suma de Minkowski entre polígonos convexos y no convexos. Finalmente,
introducimos la herramienta desarrollada para el cálculo y lavisualización de las Sumas de
Minkowski.

2. Sumas de Minkowski y sus aplicaciones
Dados dos conjuntos P y Q ⊂ R2, la suma de Minkowski de P y Q, denotada por P ⊕ Q se
define como P ⊕ Q = { p + q : p ∈ P, q ∈Q } donde p + q es un vector que representa la suma de
los vectores p y q. Es decir que dados los puntos p = ( px, py ) y q = ( qx, qy ), tenemos que
p + q = ( px + qx, py + qy).
En las figura...