TY - GEN
T1 - On t-hulls and related problems
AU - Cole, Richard
AU - Sharir, Micha
AU - Yap, Chee K.
N1 - Funding Information:
~.~y s~:-p~-~!b y a Sra~ ftam the U.S.-hraeli B/natimal ScienceF oundation. s wczki s dane under the aUSl~CeSc t the NYU/CL~SL ab~a~y f~ Robotics and ExperimemalC omput~ Science,w l-~chi s SUt4,.~-L~:bI y gr~s from Di-giud Equipmmt G,,z.~im, Tae Siren Foundat~an, and ONR grant No. N00014-82-K-038L
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 -