We show how to construct an arrangement of n lines having a monotone path of length O(n2-(d/vlog n)), where d>0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.

Lo and Steiger resolved the complexity question for computing a planar ham-sandwich cut by giving an optimal linear-time algorithm. We show how to generalize the ideas to every fixed dimension d > 2 by describing an algorithm that computes a ham-sandwich cut in Rd in time O(nd–1–a(d)), for some a(d) > 0 (going to zero as d increases). For d = 3,4, the running time is almost proportional to ed–1(n;n/2), where dd(k;n) denotes the maximal number of k-sets over sets of n points in Rd, and with the current best bounds, we get O(n3/2 log2n/log n) running time for d = 3 and O(n8/3+e) for d=4. We also give a linear time algorithm for three dimensional ham-sandwich cuts when the three sets are suitably separated.

Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane II that separates X from X/sup c/. It is proved that O(n square root k/log/sub */k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of P. Erdos et al. (A Survey of Combinatorial Theory, North-Holland, 1983, p.139-49) by a factor of log/sub */k. The method can be extended to give the bound O(n square root k/(log k)/sup epsilon /). The proof only establishes the weaker result; it uses the geometry and combinatorics together in a stronger way than in the earlier work.>

Given n points in the plane and an integer k, the problem of selecting that pair of points that determines the line with the kth smallest or largest slope is considered. In the restricted case, where k is $O(n)$, line sweeping gives an optimal, $O(n\log n)$-time algorithm. For general k the parametric search technique of Megiddo is used to describe an $O(n(\log n)^2 )$-time algorithm. This is modified to produce a new, optimal $O(n\log n)$-time selection algorithm by incorporating an approximation idea.

Infinite sets P and Q of primes are described, P ⊂ Q. For any natural number n it can be decided if n ∈ P in (deterministic) time Ο((log n)9). This answers affirmatively the question of whether there exists an infinite set of primes whose membership can be tested in polynomial time, and is the main result of the paper. Also, for every n ∈ Q, we show how to produce at random, in expected time Ο((log n)3), a certificate of length Ο(log n) which can be verified in (deterministic) time Ο((log n)3); this is less than the time needed for two exponentiations and is much faster than existing methods. Finally it is important that P is relatively dense (at least cn2/3/log n elements less than n). Elements of Q in a given range may be generated quickly, but it would be costly for an adversary to search Q in this range; this could be useful in cryptography.

We consider the problem of element distinctness. Here n synchronized processors, each given an integer input, must decide whether these integers are pairwise distinct, while communicating via an infinitely large shared memory. If simultaneous write access to a memory cell is forbidden, then a lower bound of $\Omega ( \log n )$ on the number of steps easily follows (from S. Cook, C. Dwork, and R. Reischuk, SIAM J. Comput., 15 (1986), pp. 87–97.) When several (different) values can be written simultaneously to any cell, then there is an simple algorithm requiring $O ( 1 )$ steps. We consider the intermediate model, in which simultaneous writes to a single cell are allowed only if all values written are equal. We prove a lower bound of $\Omega ( ( \log n )^{1 /2} )$ steps, improving the previous lower bound of $\Omega ( \log \log \log n )$ steps (F. E. Fich, F. Meyer auf der Heide, and A. Wigderson, Adv. in Comput., 4 (1987), pp. 1–15). The proof uses Ramsey-theoretic and combinatorial arguments. The result implies a separation between the powers of some variants of the PRAM model of parallel computation.

We show that in the deterministic comparison model for parallel computation, n processors can select the k th smallest item from a set of n numbers in O(loglogn) parallel time.With this result all comparison tasks (selection, merging, sorting), now have upper and lower bounds of the same order in both random and deterministic models.