On t-hulls and related problems

Richard Cole, Micha Sharir, Chee K. Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984
PublisherAssociation for Computing Machinery
Pages154-166
Number of pages13
ISBN (Electronic)0897911334
DOIs
StatePublished - Dec 1 1984
Event16th Annual ACM Symposium on Theory of Computing, STOC 1984 - Washington, United States
Duration: Apr 30 1984May 2 1984

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other16th Annual ACM Symposium on Theory of Computing, STOC 1984
CountryUnited States
CityWashington
Period4/30/845/2/84

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'On t-hulls and related problems'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., Sharir, M., & Yap, C. K. (1984). On t-hulls and related problems. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984 (pp. 154-166). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800057.808677