---
res:
bibo_abstract:
- 'Anarrangement ofn lines (or line segments) in the plane is the partition of the
plane defined by these objects. Such an arrangement consists ofO(n 2) regions,
calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly,
using subquadratic space and preprocessing, so that, given any query pointp, we
can calculate efficiently the face containingp. First, we consider the case of
lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer
face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved
with high probability.) In the process, we solve three interesting subproblems:
(1) given a set ofn points, find a straight-edge spanning tree of these points
such that any line intersects only a few edges of the tree, (2) given a simple
polygonal path , form a data structure from which we can find the convex hull
of any subpath of quickly, and (3) given a set of points, organize them so that
the convex hull of their subset lying above a query line can be found quickly.
Second, using random sampling, we give a tradeoff between increasing space and
decreasing query time. Third, we extend our structure to report faces in an arrangement
of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing
time. Lastly, we note that our techniques allow us to computem faces in an arrangement
ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Leonidas
foaf_name: Guibas, Leonidas
foaf_surname: Guibas
- foaf_Person:
foaf_givenName: John
foaf_name: Hershberger, John
foaf_surname: Hershberger
- foaf_Person:
foaf_givenName: Raimund
foaf_name: Seidel, Raimund
foaf_surname: Seidel
- foaf_Person:
foaf_givenName: Micha
foaf_name: Sharir, Micha
foaf_surname: Sharir
- foaf_Person:
foaf_givenName: Jack
foaf_name: Snoeyink, Jack
foaf_surname: Snoeyink
- foaf_Person:
foaf_givenName: Emo
foaf_name: Welzl, Emo
foaf_surname: Welzl
bibo_doi: 10.1007/BF02187742
bibo_issue: '1'
bibo_volume: 4
dct_date: 1989^xs_gYear
dct_publisher: Springer@
dct_title: Implicitly representing arrangements of lines or segments@
...