Zvezdasti poligon
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.[1] 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.[1] Medjutim, za slučaj jezgra mnogougla,postoji brži metod: Lee & Preparata 1979[2] koji nalazi jezgro u linearnom vremenu.
Vidite još[уреди | уреди извор]
Reference[уреди | уреди извор]
- ^ а б Franco P. Preparata; Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. 1st edition. ISBN 978-0-387-96131-6. ; 2nd printing, corrected and expanded. 1988. ISBN 978-3-540-96131-4..
- ^ Lee, D. T.; Preparata, F. P. (jul 1979), „An Optimal Algorithm for Finding the Kernel of a Polygon”, Journal of the ACM, 26 (3): 415—421, doi:10.1145/322139.322142
Literatura[уреди | уреди извор]
- Franco P. Preparata; Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. 1st edition. ISBN 978-0-387-96131-6. ; 2nd printing, corrected and expanded. 1988. ISBN 978-3-540-96131-4..