Browse Prior Art Database

ON K-HULLS AND RELATED PROBLEMS

IP.com Disclosure Number: IPCOM000128191D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 20 page(s) / 62K

Publishing Venue

Software Patent Institute

Related People

Richard Cole: AUTHOR [+5]

Abstract

For any set X of points ('in any dimension) and any k = 1, 2,..., we intro. dace the concept of the k-hull of X. This unifies the well-IuZawn nation of `convex hulls' with the notion of 'craters' recently introduced by F.F. Yao. The concept is intimately related to some other concepts , (k-belts, k-sets) studied. by E,delsbrunner, We1zI, Lovfisz, Erdcis and others. Several computational problems related to k-hulls arc studied here. Borne 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 Megidda's teduiique 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. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel; partially supported by a grant from the U.S.-Israeli Binational Science Foundation. fiIhis work is done under the auspices of the NYUIGdvIS, Laboratory for Robotics and Experimental Computer Silence, which is supported by grants from Digital Equipment Corporation, The Sloan Foundation, and ONR grant No. N1aJ014-S2-Y.-0381.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 20

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON K-HULLS AND RELATED PROBLEMS

by Richard Cole, Micha Sharir and Chee K. Yap

Technical Report No. 108 Robotics Report No. 17 February, On k-huDs end ReIated t'roblemst

Richard Cole Micha Sharfri Chrt K. Yap Courant Institute of Mathematical Sciencm, New York University, 251, Mercer Street, New York, NY 10012.

ABSTRACT

For any set X of points ('in any dimension) and any k = 1, 2,..., we intro. dace the concept of the k-hull of X. This unifies the well-IuZawn nation of `convex hulls' with the notion of 'craters' recently introduced by F.F. Yao. The concept is intimately related to some other concepts , (k- belts, k-sets) studied. by E,delsbrunner, We1zI, Lovfisz, Erdcis and others. Several computational problems related to k-hulls arc studied here. Borne 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 Megidda's teduiique 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. School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel; partially supported by a grant from the U.S.-Israeli Binational Science Foundation. fiIhis work is done under the auspices of the NYUIGdvIS, Laboratory for Robotics and Experimental Computer Silence, which is supported by grants from Digital Equipment Corporation, The Sloan Foundation, and ONR grant No. N1aJ014-S2-Y.-0381.

1. Introduction

In this paper we study the computational properties of three related concepts: k-hulls, a- partitioners and the `Ham Sandwich cut'. The naturalness of th~= notions is reinforced by tlae fact that they are intimately related to other concepts studied elsewhere. Furtire=ore, effiderat a algorithm related to these objects have applications to problems arising in different ways. In this introduction, we define these concepts. Let X be a set of n planar points. A point p inside the convex lriil of X can be characterized by the property that any line through p has at least a paint of ,Y in each of the closed half-planet/ deterrli-ned by the line. Generalizing this, we define the k- faU (k > 0) of X as thy set of poiW,s p smh that any line through p has at least k paints of X on each cle:zd half-pIamc. Clearly the r:- huIl contains the k+1-hull, and if k > n/2 then the k-bolt is empty. An easy consequence, of 13e11y's theorem jYB] shows that the k-hull is always non- empty for

(Equation Omitted)

be known as the center of X in this (extreme) case. Ixenceforth we asstime

New York University Page 1 Dec 31, 1984

Page 2 of 20

ON K-HULLS AND RELATED PROBLEMS

(Equation Omitted)

(unle...