TY - GEN

T1 - On t-hulls and related problems

AU - Cole, Richard

AU - Sharir, Micha

AU - Yap, Chee K.

N1 - Publisher Copyright:
© 1984 ACM.

PY - 1984/12/1

Y1 - 1984/12/1

N2 - For any set X of points (in any dimension) and any k= 1, 2,..., we introduce the concept of the k-bull 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 Edelsbronner, Welzl, Lovász, Erdös and others. Several computational problems related to k-hulls are studied here. Some of our algorithms are of interest in themselves because of the techniques employed; in particular, the 'parametric' searching technique of Megiddo is used in a non- Trivial way. We will also extend Megiddo's technique to Las Vegas algorithms. Our results have applications to a variety of problems in computational geometry: 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.

AB - For any set X of points (in any dimension) and any k= 1, 2,..., we introduce the concept of the k-bull 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 Edelsbronner, Welzl, Lovász, Erdös and others. Several computational problems related to k-hulls are studied here. Some of our algorithms are of interest in themselves because of the techniques employed; in particular, the 'parametric' searching technique of Megiddo is used in a non- Trivial way. We will also extend Megiddo's technique to Las Vegas algorithms. Our results have applications to a variety of problems in computational geometry: 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.

UR - http://www.scopus.com/inward/record.url?scp=85034847006&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034847006&partnerID=8YFLogxK

U2 - 10.1145/800057.808677

DO - 10.1145/800057.808677

M3 - Conference contribution

AN - SCOPUS:85034847006

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 154

EP - 166

BT - Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984

PB - Association for Computing Machinery

T2 - 16th Annual ACM Symposium on Theory of Computing, STOC 1984

Y2 - 30 April 1984 through 2 May 1984

ER -