Poligon în formă de stea
Un poligon în formă de stea este o figură poligonală plană a cărei formă corespunde unui domeniu stea, adică un poligon care conține cel puțin un punct din care întreaga frontieră a poligonului este vizibilă.
Formal, un poligon P are formă de stea dacă există un punct z astfel încât pentru fiecare punct p din P segmentul zp se află în întregime în P.[1] Mulțimea tuturor punctelor z cu această proprietate (adică mulțimea de puncte din care toate punctele lui P sunt vizibile) se numește nucleul lui P.
Dacă un poligon în formă de stea este convex, distanța legăturii dintre oricare două dintre punctele sale (numărul minim de segmente ale unei linii poligonale care poate conecta acele puncte) este de 1, deci distanța legăturii este de 1 pentru toate diametrele. Dacă un poligon în formă de stea nu este convex, distanța legăturii dintre un punct din nucleu și orice alt punct din poligon este de 1, în timp ce distanța legăturii dintre oricare două puncte care sunt în poligon, dar în afara nucleului este fie de 1, fie de 2; în acest caz, distanța maximă de legătură este de 2.
Exemple
[modificare | modificare sursă]Un poligon convex este în formă de stea, iar nucleul său corespunde cu poligonul însuși.
Poligoanele stelate sunt în formă de stea, centrul lor fiind situat întotdeauna în nucleul lor.
Antiparalelogramele și hexagoanele Lemoine, care se autointersectează, sunt poligoane în formă de stea, cu nucleul format dintr-un singur punct.
Poligoanele de vizibilitate(d) sunt în formă de stea, deoarece fiecare punct al lor trebuie să fie vizibil din centru prin definiție.
Algoritmi
[modificare | modificare sursă]Testarea dacă un poligon are formă de stea și găsirea unui singur punct din nucleu poate fi rezolvată în timp liniar prin formularea problemei în termenii programării liniare și aplicarea tehnicilor de programare liniară pentru dimensiuni mici.[2]
Fiecare latură a unui poligon definește un semiplan interior, semiplanul a cărui frontieră se află pe dreapta care conține latura și care conține punctele poligonului într-o vecinătate a oricărui punct interior al laturii. Nucleul unui poligon este intersecția tuturor semiplanelor sale interioare. Intersecția unei mulțimi arbitrare de N semiplane poate fi găsită în timp Θ(N log N) folosind metoda divide et impera.[1] Totuși, în cazul nucleelor de poligoane este posibilă o metodă mai rapidă, Lee și Preparata prezentând în 1979 un algoritm pentru obținerea nucleului în timp liniar.[3]
Note
[modificare | modificare sursă]- ^ a b Preparata, Franco P.; Shamos, Michael Ian (). Computational Geometry – An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 1st edition: ; 2nd printing, corrected and expanded, 1988.
- ^ Jiří Matoušek, Micha Sharir, Emo Welzl, A Subexponential Bound for Linear Programming, Algorithmica 16, (1996), 498-51, accesat 2021-11-09
- ^ Lee, Der-Tsai; Preparata, Franco P. (iulie 1979), „An Optimal Algorithm for Finding the Kernel of a Polygon”, Journal of the ACM, 26 (3): 415–421, doi:10.1145/322139.322142, hdl:2142/74090
, arhivat din original la , accesat în
