Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2019

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: geodesic center

Sortuj według:

Ogranicz wyniki do:

Geodesic Center of a Simple Polygon using a Logarithmic Number of Extra Variables

Kavand P., Mohades A.

Fundamenta Informaticae

2019

Vol. 169, nr 3

211--235

In this paper, we propose an algorithm for computing the geodesic center of a simple polygon when the available workspace is limited. Our algorithm is a memory-constrained algorithm which has read-only access to the input. In addition to the input, it uses Θ(log n) words of O(log n) bits for reading and writing. The algorithm runs in O(n4) expected time, where n is the number of the corners of the polygon. We also show that the geodesic farthestsite Voronoi diagram of the corners of the polygon can be computed in the same time and space. As a sub-result, we present an s-workspace algorithm for finding a geodesic farthest neighbor of a given point inside a simple polygon which runs in O(n2/s) expected time where s∈Ω(log n)∩O([formula]).