| Property |
Value |
| dbo:abstract
|
- En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclidiano fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos. Un algoritmo ingenuo para resolver el problema consiste en "calcular las distancias entre todos los pares de puntos del conjunto y seleccionar el mínimo", que requiere un tiempo O(n^2). Pero resulta que el problema puede ser solucionado en tiempo O(n log n) en un espacio euclídeo. Este tiempo puede incluso ser mejorado: Si asumimos que la función de parte entera (floor) es computable en tiempo constante, el problema puede ser solucionado en tiempo O(n log log n). Si además permitimos utilizar aleatorización, el problema puede ser solucionado en tiempo O(n). (es)
- En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclidiano fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos. Un algoritmo ingenuo para resolver el problema consiste en "calcular las distancias entre todos los pares de puntos del conjunto y seleccionar el mínimo", que requiere un tiempo O(n^2). Pero resulta que el problema puede ser solucionado en tiempo O(n log n) en un espacio euclídeo. Este tiempo puede incluso ser mejorado: Si asumimos que la función de parte entera (floor) es computable en tiempo constante, el problema puede ser solucionado en tiempo O(n log log n). Si además permitimos utilizar aleatorización, el problema puede ser solucionado en tiempo O(n). (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:autor
|
- Jon Kleinberg; Éva Tardos (es)
- Jon Kleinberg; Éva Tardos (es)
|
| prop-es:año
| |
| prop-es:editorial
|
- Addison Wesley (es)
- Addison Wesley (es)
|
| prop-es:título
|
- Algorithm Design (es)
- Algorithm Design (es)
|
| dct:subject
| |
| rdfs:comment
|
- En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclidiano fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos. (es)
- En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclidiano fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos. (es)
|
| rdfs:label
|
- Problema del par de puntos más cercanos (es)
- Problema del par de puntos más cercanos (es)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
