From Sorting to Convex Hull
Jérémy Barbay 7 Abr 201007/04/10 a las 11:59 hrs.2010-04-07 11:59:07
**** From Sorting to Convex Hull
<2010-04-06 Tue 14:30-16:00>
1. Algoritmos de Ordenamiento:
- Review/Summary of what we saw.
2. Problema de Ordenamiento
- Lower Bounds for Problems
- Optimality of Algorithms
- Comparation of Difficulty Measures
- Fixed Problem
- Variable Problem (Pb,m)
3. Sorting in higher dimentsion
- not well defined, many interpretations are possible
- *Max Vector* in the plane
- Given a set of points, find the set of dominant points.
- a point v is *dominated* by a point w if
- v.x < w.x and v.y < w.y
- a *dominant* point is not dominated by any other point.
- There exits a simple algorithm:
- sort by x O(n lg n )
- "wrap around" O(n)
- total complexity O(n lg n)
- *Convex Hull* in the plane
- Given a set of points, find the smallest convex polygon
containing those points
- There exist the same simple algorithm as for Max Vector,
with complexity O(n lg n)
4. TAREA:
- What could be good measures of difficulty for MaxVector and
Convex Hull?
<2010-04-06 Tue 14:30-16:00>
1. Algoritmos de Ordenamiento:
- Review/Summary of what we saw.
2. Problema de Ordenamiento
- Lower Bounds for Problems
- Optimality of Algorithms
- Comparation of Difficulty Measures
- Fixed Problem
- Variable Problem (Pb,m)
3. Sorting in higher dimentsion
- not well defined, many interpretations are possible
- *Max Vector* in the plane
- Given a set of points, find the set of dominant points.
- a point v is *dominated* by a point w if
- v.x < w.x and v.y < w.y
- a *dominant* point is not dominated by any other point.
- There exits a simple algorithm:
- sort by x O(n lg n )
- "wrap around" O(n)
- total complexity O(n lg n)
- *Convex Hull* in the plane
- Given a set of points, find the smallest convex polygon
containing those points
- There exist the same simple algorithm as for Max Vector,
with complexity O(n lg n)
4. TAREA:
- What could be good measures of difficulty for MaxVector and
Convex Hull?
| Última Modificación | 7 Abr 201007/04/10 a las 11:59 hrs.2010-04-07 11:59:07 |
|---|---|
| Vistas Únicas | 0 |
| Compartir | |
| Comentarios |
|
