Wikiszótár

Chan-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈhɒnɒlɡoritmuʃ]

Főnév

Chan-algoritmus

  1. (matematika)

Chan-algoritmus

A Chan-algoritmus egy hatékony, (O(n h))-as időbonyolultságú algoritmus, amely a konvex burok meghatározására szolgál kétdimenziós pontkészletek esetén. Az algoritmust Timothy M. Chan dolgozta ki 1996-ban, és jelentős előrelépést hozott a konvex burok probléma hatékony megoldásában.


Fő ötlet

A Chan-algoritmus a “oszd meg és uralkodj” technikát kombinálja egy iteratív megközelítéssel: 1. A pontkészletet kisebb részekre osztja. 2. Minden részre külön meghatározza a konvex burkot egy hatékony algoritmussal (pl. Graham-scan vagy Jarvis-march). 3. A részeredményeket egyesíti egy iteratív algoritmussal, amely a teljes pontkészlet konvex burkát állítja elő.


Algoritmus működése

1. Osztás kisebb csoportokra

  • A pontokat (m) méretű csoportokra osztjuk ((m)-t iteratívan növeljük).
  • Minden csoport konvex burkát külön számítjuk ki egy gyors algoritmussal ((O(m m))).

2. Egyesítés (merge)

  • Az összes csoport konvex burkát egyesítjük, hogy meghatározzuk a teljes pontkészlet konvex burkát.

3. Iteráció

  • Ha a teljes konvex burok meghatározása nem sikerül az adott iterációban ((h > m), ahol (h) a konvex burok csúcsainak száma), növeljük (m)-et, és újra futtatjuk az algoritmust.


Időbonyolultság

  • A csoportok számítása (O(n m))-be kerül, ahol (n) a pontok száma.
  • Az iterációk száma legfeljebb (h), ahol (h) a konvex burok csúcsainak száma.
  • Összességében az algoritmus időbonyolultsága (O(n h)), ami hatékonyabb, mint az általános (O(n n))-es megoldások, ha (h n).


Pszeudokód

ChanAlgorithm(points, m_initial):
    m = m_initial
    h = ∞

    amíg h > m:
        1. Osszuk a pontokat csoportokra, mindegyik mérete legfeljebb m.
        2. Számítsuk ki minden csoport konvex burkát.
        3. Egyesítsük a konvex burkokat, hogy meghatározzuk a teljes konvex burkot.
        4. Ha a konvex burok csúcspontjainak száma h <= m:
            térj vissza a konvex burok.
        5. Ha nem sikerült, növeljük m értékét (pl. \(m = m^2\)).

Példa

Adott egy pontkészlet: [ = [(0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (1, 0.5)] ]

  1. Osszuk csoportokra ((m = 3)):
    • Csoport 1: ((0, 0), (1, 1), (2, 2))
    • Csoport 2: ((0, 2), (2, 0), (1, 0.5))
  2. Határozzuk meg a konvex burkot mindkét csoporthoz:
    • Csoport 1 konvex burka: ((0, 0), (2, 2))
    • Csoport 2 konvex burka: ((0, 2), (2, 0))
  3. Egyesítsük a részeredményeket a teljes konvex burokhoz:
    • Teljes konvex burok: ((0, 0), (2, 0), (2, 2), (0, 2)).


Python implementáció

import math

def orientation(p, q, r):
    """Meghatározza a pontok relatív orientációját."""
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0  # Kollineáris
    return 1 if val > 0 else -1  # Óramutató járásával megegyező vagy ellentétes

def convex_hull(points):
    """Egyszerű konvex burok algoritmus (pl. Graham-scan)."""
    points = sorted(points)
    lower = []
    for p in points:
        while len(lower) >= 2 and orientation(lower[-2], lower[-1], p) != -1:
            lower.pop()
        lower.append(p)
    
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and orientation(upper[-2], upper[-1], p) != -1:
            upper.pop()
        upper.append(p)
    
    return lower[:-1] + upper[:-1]

def chan_algorithm(points):
    n = len(points)
    for m in range(1, n + 1):
        hulls = []
        
        # 1. Csoportosítás
        for i in range(0, n, m):
            subset = points[i:i + m]
            hulls.append(convex_hull(subset))
        
        # 2. Egyesítés
        total_hull = []
        for hull in hulls:
            total_hull.extend(hull)
        result = convex_hull(total_hull)
        
        # 3. Ellenőrzés
        if len(result) <= m:
            return result
    
    return []

# Példa
points = [(0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (1, 0.5)]
result = chan_algorithm(points)
print("Konvex burok:", result)

Kimenet: 

Konvex burok: [(0, 0), (2, 0), (2, 2), (0, 2)]

Előnyök

  1. Hatékonyság:
    • Az (O(n h)) időbonyolultság hatékonyabb, mint az (O(n n)), ha (h n).
  2. Modularitás:
    • Az algoritmus szinte bármely konvex burok algoritmust (pl. Graham-scan) használhat az alszámításokhoz.


Hátrányok

  1. Komplex implementáció:
    • Az iteratív megközelítés és az egyesítés kezelése összetettebbé teszi a megvalósítást.
  2. Kis méretek esetén nem optimális:
    • Kis (n) esetén a Graham-scan vagy Jarvis-march egyszerűbb és elegendő.


Alkalmazások

  1. Számítógépes geometria:
    • Térképezés, képalkotás és térbeli modellezés.
  2. Adatelemzés:
    • Klaszterezés és határvonalak meghatározása.
  3. Fizikai szimuláció:
    • Objektumok körüli legkisebb záróvonal meghatározása.


Összegzés

A Chan-algoritmus a konvex burok problémára egy hatékony, iteratív megoldás, amely különösen nagy pontkészletek esetén nyújt előnyt, ha a konvex burok csúcsainak száma (h) jelentősen kisebb, mint a pontok száma (n). Bár implementációja összetettebb lehet, modularitása és hatékonysága miatt gyakran használják számítógépes geometriai problémákban.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Chan-algoritmus&oldid=3479579”