| Property |
Value |
| dbo:abstract
|
- En geometría computacional el problema de intersección de segmentos de recta está dado de la siguiente manera: dado un conjunto de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto . Mucha de la motivación para el estudio de los problemas de intersección recae en el simple hecho de que dos cuerpos no pueden ocupar el mismo lugar. La importancia de estudiar y diseñar algoritmos eficientes para detectar intersecciones está dada por la ambición de la industria, una imagen complicada puede contener cientos de miles de vectores. Una base de datos puede contener más de un millón de elementos, un circuito integrado puede contener millones de componentes; en estos casos tener un algoritmo inclusive de complejidad cuadrática son inaceptables. En geometría existen problemas los cuales puede ser resueltos mediante la solución del problema de intersección de segmentos como pueden ser el decidir cuando un polígono es simple o no. Un primer intento en resolver este problema está dado por lo siguiente: tomar todas las parejas de segmentos y ver si se intersecan. Este método es de orden (se dice que este algoritmo usa fuerza bruta, pues prueba todas las opciones posibles). A primera instancia es un algoritmo óptimo; sin embargo, es de orden , es decir, aun si no se presenta alguna intersección el algoritmo toma tiempo cuadrático. Es necesario un algoritmo "output sensitive" (sensible a la salida) para reducir este tiempo a algo cercano a (es)
- En geometría computacional el problema de intersección de segmentos de recta está dado de la siguiente manera: dado un conjunto de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto . Mucha de la motivación para el estudio de los problemas de intersección recae en el simple hecho de que dos cuerpos no pueden ocupar el mismo lugar. La importancia de estudiar y diseñar algoritmos eficientes para detectar intersecciones está dada por la ambición de la industria, una imagen complicada puede contener cientos de miles de vectores. Una base de datos puede contener más de un millón de elementos, un circuito integrado puede contener millones de componentes; en estos casos tener un algoritmo inclusive de complejidad cuadrática son inaceptables. En geometría existen problemas los cuales puede ser resueltos mediante la solución del problema de intersección de segmentos como pueden ser el decidir cuando un polígono es simple o no. Un primer intento en resolver este problema está dado por lo siguiente: tomar todas las parejas de segmentos y ver si se intersecan. Este método es de orden (se dice que este algoritmo usa fuerza bruta, pues prueba todas las opciones posibles). A primera instancia es un algoritmo óptimo; sin embargo, es de orden , es decir, aun si no se presenta alguna intersección el algoritmo toma tiempo cuadrático. Es necesario un algoritmo "output sensitive" (sensible a la salida) para reducir este tiempo a algo cercano a (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:apellido
|
- Overmars (es)
- Berg (es)
- van Kreveld (es)
- Cheong (es)
- Preparata (es)
- Shamos (es)
- Overmars (es)
- Berg (es)
- van Kreveld (es)
- Cheong (es)
- Preparata (es)
- Shamos (es)
|
| prop-es:año
|
- 1985 (xsd:integer)
- 2008 (xsd:integer)
|
| prop-es:edición
|
- tercera (es)
- tercera (es)
|
| prop-es:editorial
|
- Springer-Verlag Berlin Heidelberg (es)
- Springer-Verlag New York Inc. (es)
- Springer-Verlag Berlin Heidelberg (es)
- Springer-Verlag New York Inc. (es)
|
| prop-es:id
|
- ISBN 0-387-96131-3 (es)
- ISBN 978-3-540-77973-5 (es)
- ISBN 0-387-96131-3 (es)
- ISBN 978-3-540-77973-5 (es)
|
| prop-es:nombre
|
- Marc (es)
- Mark (es)
- Otfried (es)
- Franco P. (es)
- Mark de (es)
- Michael Ian (es)
- Marc (es)
- Mark (es)
- Otfried (es)
- Franco P. (es)
- Mark de (es)
- Michael Ian (es)
|
| prop-es:título
|
- Computational Geometry, Algorithms and Applications (es)
- Computational Geometry, An Introduction (es)
- Computational Geometry, Algorithms and Applications (es)
- Computational Geometry, An Introduction (es)
|
| prop-es:url
| |
| dct:subject
| |
| rdfs:comment
|
- En geometría computacional el problema de intersección de segmentos de recta está dado de la siguiente manera: dado un conjunto de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto . (es)
- En geometría computacional el problema de intersección de segmentos de recta está dado de la siguiente manera: dado un conjunto de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto . (es)
|
| rdfs:label
|
- Intersección de segmentos de recta (es)
- Intersección de segmentos de recta (es)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
