Anzeige
Erschienen in:
07.11.2018
Efficient algorithms for computing one or two discrete centers hitting a set of line segments
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2019
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given the scheduling model of bike-sharing, we consider the problem of hitting a set of n axis-parallel line segments in \(\mathbb {R}^2\) by a square or an \(\ell _\infty \)-circle (and two squares, or two \(\ell _\infty \)-circles) whose center(s) must lie on some line segment(s) such that the (maximum) edge length of the square(s) is minimized. Under a different tree model, we consider (virtual) hitting circles whose centers must lie on some tree edges with similar minmax-objectives (with the distance between a center to a target segment being the shortest path length between them). To be more specific, we consider the cases when one needs to compute one (and two) centers on some edge(s) of a tree with m edges, where n target segments must be hit, and the objective is to minimize the maximum path length from the target segments to the nearer center(s). We give three linear-time algorithms and an \(O(n^2\log n)\) algorithm for the four problems in consideration.