On k-hulls and related problems
Published 1 January 1984Open access
Richard Cole, Micha Sharir, Chee Yap
Citations42
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Efficient computation of the 'cut' guaranteed by the classical 'Ham Sandwich theorem', faster preprocessing time for polygon retrieval, and theoretical improvements to a problem of intersecting lines and points posed by Hopcroft.
Abstract
For any set X of points (in any dimension) and any k = 1,2, ..., we introduce the concept of the k-hull of X. This unifies the well-known notion of 'convex hulls' with the notion of 'centers' recently introduced by F.F. Yao. The concept is intimately related to some other concepts (k-belts, k-sets) studied by Edelsbrunner, Welzl, Lovász, Erdös and others.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
An 0(n log n) sorting network
665 Citations1983Miklós Ajtai, János Komlós +1 more
A sorting network of size 0(n log n) and depth 0(log n) is described, and a derived procedure (&egr;-nearsort) are described below, and the sorting network will be centered around these elementary steps.
Journal of the ACMApplying Parallel Computation Algorithms in the Design of Serial Algorithms
632 Citations1983Nimrod Megiddo
It is pointed out that analyses of parallelism in computational problems have practical implications even when multi-processor machines are not available, and a unified framework for cases like this is presented.
Journal of Computer and System SciencesMaintenance of configurations in the plane
462 Citations1981Mark H. Overmars, Jan Van Leeuwen
A fully dynamic maintenance algorithm for convex hulls that can process insertions and deletions of single points in only O(log* n) steps per transaction, where n is the number of points currently in the set.
SIAM Journal on ComputingParallelism in Comparison Problems
400 Citations1975Leslie G. Valiant
The worst-case time complexity of algorithms for multiprocessor computers with binary comparisons as the basic operations is investigated and the algorithm for finding the maximum is shown to be optimal for all values of k and n.
American Mathematical MonthlyHow to Cut a Cake Fairly
349 Citations1961Lester E. Dubins, Edwin H. Spanier
Theoretical Computer ScienceFinding the intersection of two convex polyhedra
292 Citations1978David E. Muller, F. P. Preparata
An algorithm to test whether their intersection is empty, and if so to find a separating plane, and to construct their intersection polyhedron is developed, which runs in timeO (n log n), where n is the sum of the numbers of vertices of the two polyhedra.
Elsevier eBooksDissection Graphs of Planar Point Sets
179 Citations1973Péter L. Erdős, László Lovász +2 more
IEEE Transactions on ComputersNew Parallel-Sorting Schemes
160 Citations1978Preparata
A family of parallel-sorting algorithms for a multiprocessor system that is enumeration sortings and includes the use of parallel merging to implement count acquisition, matching the performance of Hirschberg's algoithm, which, however, is not free of fetch conflicts.
Journal of Combinatorial Theory Series AOn the number of line separations of a finite set in the plane
78 Citations1985Herbert Edelsbrunner, Emo Welzl
The asymptotic behaviour of f k ( n) is studied as this function has applications to a number of problems in computational geometry and a lower and an upper bound on fk ( n ) is established.
A 3-space partition and its applications
62 Citations1983Fei Yao
It is shown that one can always find three planes that divide S into eight open regions, of which no seven together contain more than n points, which gives rise to a data structure, what is called an octant-tree, for representing any point set in 3-space.
Information Processing LettersA parallel median algorithm
44 Citations1985Richard Cole, Chee Yap
A deterministic algorithm for finding the k th smallest item in a set of n items, running in O log log n 2 parallel time on O(n) processors in Valiant's comparison model is given.