Implicitly representing arrangements of lines or segments
type: Item
instance of: scholarly article
title: Implicitly representing arrangements of lines or segments
zbMATH Open document ID: 0688.68031
DOI: 10.1007/BF02187742
author: Herbert Edelsbrunner
author: Raimund Seidel
author: Emo Welzl
author: Leonidas Guibas
author: John Hershberger
author: Micha Sharir
author: Jack Snoeyink
published in: Discrete \& Computational Geometry
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131091
review text: Line arrangements, i.e. partitions of the plane by lines find numerous applications in computational geometry. However their full representation of size \(O(n^ 2)\) is sometimes excessive. The paper deals with the basic problem of face queries: given a query point p one has to retrieve the face containing p. Via geometric duality the latter problem is transformed into one of its own interest: given a planar pointset for any query line find convex hulls of points on both sides of it quickly. The paper presents algorithms with subquadratic space and preprocessing and sublinear face query time for arrangements of lines and line segments. A tradeoff for space vs. query time is also shown possible via random sampling method. Some other related problems are also considered.
reviewed by: N.Korneenko
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4128377
zbMATH Keywords: segment arrangement
zbMATH Keywords: partition tree
zbMATH Keywords: spanning tree
zbMATH Keywords: implicit representation
zbMATH Keywords: convex hull query
zbMATH Keywords: Line arrangements
zbMATH Keywords: computational geometry
zbMATH Keywords: face queries
zbMATH Keywords: convex hulls
zbMATH Keywords: random sampling
MaRDI profile type: Publication
Wikidata QID: Q54309736
cites work: Triangles in space or building (and analyzing) castles in the air
cites work: Algorithms for Reporting and Counting Geometric Intersections
cites work: An optimal algorithm for intersecting line segments in the plane
cites work: Visibility and intersection problems in plane geometry
cites work: Fractional cascading. II: Applications
cites work: The power of geometric duality
cites work: Quasi-optimal range searching in spaces of finite VC-dimension
cites work: New applications of random sampling in computational geometry
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: Q3772828
cites work: Topologically sweeping an arrangement
cites work: Q3795219
cites work: The complexity and construction of many faces in arrangements of lines and of segments
cites work: Optimal Point Location in a Monotone Subdivision
cites work: Constructing Arrangements of Lines and Hyperplanes with Applications
cites work: Halfplanar range search in linear space and \(O(n^{0.695})\) query time
cites work: Optimal shortest path queries in a simple polygon
cites work: Q3138890
cites work: Q3796750
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Optimal Search in Planar Subdivisions
cites work: Q4057549
cites work: Spanning trees with low crossing number
cites work: Maintenance of configurations in the plane
cites work: Q3992847
cites work: Polygon Retrieval
OpenAlex ID: W1972875213
DBLP publication ID: journals/dcg/EdelsbrunnerGHSSSW89
description: scientific article; zbMATH DE number 4128377