Finding the conditional location of a median path on a tree

In this paper, we study the problem of locating a median path of limited length on a tree under the condition that some existing facilities are already located. The existing facilities may be located at any subset of vertices. Upper and lower bounds are proposed for both the discrete and continuous models. In the discrete model, a median path is not allowed to contain partial edges. In the continuous model, a median path may contain partial edges. The proposed upper bounds for these two models are O(n log n) and O(n log nα(n)), respectively. They improve the previous known bounds from O(n log² n) and O(n²), respectively. The proposed lower bounds are both Ω(n log n).     

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log²n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)²) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.     

Perceptual lane width,wide perceptual road centre markings and driving speeds

The possibility that driving speeds could be reduced through the use of lane delineation was explored. Using a high-fidelity driving simulator, 28 experienced drivers were measured on seven two-lane rural roads with lane widths of 3.6, 3.0, or 2.5?m, and with either a standard centreline (control), a wide painted hatched road centre marking, or a wide white gravel road centre marking. Driving speeds were reduced on the narrowest lane width road, and further reduced on straight road sections that contained the centre marking with painted hatching. It was concluded that the narrow lane width increased steering workload and reduced speeds through a speed-steering workload trade-off, whilst the hatched road centre marking enhanced peripheral visual speed perception, leading to higher speed estimations and slower speeds. Therefore, narrowing the lane width below 3.0?m by using a painted hatched road centre marking should be an effective way to reduce driving speeds.     

On Methods of Constructing Sets of Mutually Orthogonal Latin Squares Using a Computer. II

A new class of triplets of mutually orthogonal latin squares is derived. These are the consequence of attempts to extend the results described in Part I of this paper which appears in Technometrics, 1960, Vol. 2, No. 4, p. 507.     

Efficient algorithms for the round-trip 1-center and 1-median problems

This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset $A^i\subseteq A$ of depots that i can potentially select from and use. When $A^i=A$ for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an $O(mn\lg n)$-time algorithm. For the restricted 1-median problem, we give an $O(mn\lg (|A|/m)+n^2\lg n)$-time algorithm. For the unrestricted 1-median problem, we give an $O(mn+n^2\lg \lg n)$-time algorithm.