мини|десно|200px|Zveydasti poligon(gore). Njegovo jezgro je prikazano na slici dole. Zvezdasti poligon je mnogougao takav da takav da postoji tačka x0 iz njegove unutrašnjosti takva da duž koja spaja nju sa bilo kojom drugom tačkom skupa pripada datom skupu ,to jest, da mnogougao sadrži tacku iz koje je cela mnogougaona linija vidljiva.
Formalno, mnogougaoP je zvezdast ako postoji tacka z takva da ya svaku tacku p iz P svaka tacka duži zp pripada P. ; 2nd printing, corrected and expanded. Set svih tačaka zsa ovim svojstvom (to jest, skup tacaka iz kojih su sve tacke skupaP vidljive) zove se jezgro skupa P.
Primer Svaki konveksan mnogougao je zvezdast, i on je sam svoje jezgro.
Algoritmi Proveravanje da li je mnogougao zvedast, i nalaženje tačke iz jezgra,se može rešiti u linearnom vremenu formulisanjem problema kao linearnog i primenjivanjem tehnika linearnog programiranja.
Svako teme mnogougla definiše poluravan, poluravan cija granica leži na pravoj koja sadrži ivicu i koja sadrži tačke iz okoline neke od temena ivice mnogougla. Jezgro mnogougla je presek svih poluravni cije su granice ivice mnogougla. Presek nekih N poluravni može se naći u vremenu Θ (N log N) korišćenjem tehnike podeli pa vladaj. Medjutim, za slučaj jezgra mnogougla,postoji brži metod: koji nalazi jezgro u linearnom vremenu.
Vidite još Monotone polygon
Reference
Literatura ; 2nd printing, corrected and expanded.
Категорија:Многоуглови