Browse Prior Art Database

Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number

IP.com Disclosure Number: IPCOM000128210D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-15

Publishing Venue

Software Patent Institute

Related People

Pankaj K. Agarwal: AUTHOR [+3]

Abstract

In this paper we consider the following problem: Given a set G of rc (possibly intersecting) line segments in the plane, preprocess it so that, given a query ray p emanating from a point p, one can quickly compute the intersection point 4~ (G, p) of p with a segment of G that lies nearest to p. We present an algo- rithm that preprocesses G, in time O(n3/21og" n), into a data structure of size [Equation ommitted] so that for a query ray p, D(G,P) can be computed in time [Equation ommitted] where w is a constant G 4.33 and a(n) is a functional inverse of Ackermann's function. If the given segments are non-intersecting, the stor- age goes down to O(nlog3 n) and the query time becomes [Equation ommitted] The main tool that we use is spanning trees (on the set of segment endpoints) with low stabbing number, i.e. with the property that no line intersects more than [Equation ommitted] edges of the tree. Using such trees we also obtain faster algorithms for several other problems, including implicit point location, polygon containment and implicit hidden surface removal. tWork on this paper has been supported by Office of Naval Research Grant N00014- 87-K-0129, by National Science Foundation Grant DCR-83-200$5, and by grants from the Digital Equipment Corporation, and the IBM Corporation. - tA preliminary version of this paper appears in. Proceedings 5th Annual Symposium on Computational Geometry, 1989, pp. 315-325.

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

Page 1 of 46

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number

by

Pankaj K. Agarwal

Technical Report No. 448 Robotics Report No. 199 May, 1988 New York University Dept. of Computer Science Courant Institute of Mathematical Sciences 251 Mercer Street New York, New York 10012

Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129 National Science Foundation CER Grant DCR-83-20085, National Science Foundation Grant subcontract CMU-406349-55586, and by grants from the Digital Equipment Corpora-tion and the IBM Corporation. Ray shooting and Other Applications of Spanning Trees with Low Stabbing Number Pankaj h'. Agarwalt Courant Institute of Mathematical Sciences New York University NY 10012

ABSTRACT

In this paper we consider the following problem: Given a set G of rc (possibly intersecting) line segments in the plane, preprocess it so that, given a query ray p emanating from a point p, one can quickly compute the intersection point 4~ (G, p) of p with a segment of G that lies nearest to
p. We present an algo- rithm that preprocesses G, in time O(n3/21og" n), into a data structure of size

(Equation Omitted)

so that for a query ray p, D(G,P) can be computed in time

(Equation Omitted)

where w is a constant G 4.33 and a(n) is a functional inverse of Ackermann's function. If the given segments are non-intersecting, the stor- age goes down to O(nlog3 n) and the query time becomes

(Equation Omitted)

The main tool that we use is spanning trees (on the set of segment endpoints) with low stabbing number, i.e. with the property that no line intersects more than

(Equation Omitted)

edges of the tree. Using such trees we also obtain faster algorithms for several other problems, including implicit point location, polygon containment and implicit hidden surface removal. tWork on this paper has been supported by Office of Naval Research Grant N00014- 87-K-0129, by National Science Foundation Grant DCR-83-200$5, and by grants from the Digital Equipment

New York University Page 1 Dec 31, 1988

Page 2 of 46

Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number

Corporation, and the IBM Corporation. - tA preliminary version of this paper appears in. Proceedings 5th Annual Symposium on Computational Geometry, 1989, pp. 315-325.

INTRODUCTION

1 Introduction In the last few years many efficient randomized algorithms, based on the random sampling techniques of [ClJ or on the related e-net theory [HWJ, have been developed to solve efficiently a variety of geometric problems. One such recent development is due to Welzl ([We]; see also (CWJ), who showed that, for a given set S of n points in the plane, there exists a spanning tree T of S, such that no line intersects more than O(Vfn- log n) edges of T. Such a tree T is called a spanning tree with low stabbing number (a formal definition is given in Section
2). Welzl used spanni...