Ruci, E: On a Class of 3SUM-HARD problems in ComputationalGe
-
- Englisch ausgewählt
43,99 €
UVP
49,00 €
inkl. gesetzl. MwSt.,
Beschreibung
Produktdetails
Einband
Taschenbuch
Verlag
VDMSeitenzahl
76
Maße (L/B/H)
22/15/0,5 cm
Gewicht
119 g
Sprache
Englisch
ISBN
978-3-639-15837-3
want to compute the set of
straight lines in the Cartesian plane that cut this
polygon into exactly K simple
polygons. We call this set of lines a K-separator and
call this problem the K-separator
problem.
We present an algorithm that finds the K-separators
of an n-vertex simple polygon,
for all K 0, in O(n2) total time.
We prove that the decision problem given an integer K 2 and an edge of the
polygon, is there a line through this edge that cuts
the polygon in exactly K pieces?, is
3SUM-HARD. For the special case when K = 2, we show
that the decision problem
can be solved in O(n log(n)) time.
Several other complexity results may be obtained. We
suspect that the problem
of finding the cell of maximum depth is also
3SUM-hard, and as a corollary the
problem of identifying the line that cuts the polygon
in the maximum possible number
of pieces is also 3SUM-hard.
Noch keine Bewertungen vorhanden
Verfassen Sie die erste Bewertung zu diesem Artikel
Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.
Kurze Frage zu unserer Seite
Vielen Dank für dein Feedback
Wir nutzen dein Feedback, um unsere Produktseiten zu verbessern. Bitte habe Verständnis, dass wir dir keine Rückmeldung geben können. Falls du Kontakt mit uns aufnehmen möchtest, kannst du dich aber gerne an unseren Kund*innenservice wenden.
zum Kundenservice