Name
Title | ||
|---|---|---|
Efficient algorithms for computing one or two discrete centers hitting a set of line segments |
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10878-018-0359-6 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
One or two discrete centers problem, Hit line segments, Computational geometry | Line segment,Binary logarithm,Combinatorics,Shortest path problem,Path length,Scheduling (computing),Computational geometry,Algorithm,Decision tree model,Mathematics | Journal |
Volume | Issue | ISSN |
37 | 4 | 1573-2886 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaozhou He | 1 | 0 | 0.34 |
| Zhihui Liu | 2 | 0 | 0.34 |
| Bing Su | 3 | 17 | 4.72 |
| Yinfeng Xu | 4 | 1636 | 108.18 |
| Feifeng Zheng | 5 | 214 | 42.51 |
| Binhai Zhu | 6 | 903 | 109.96 |