Connected component and simple polygon intersection searching

DOI10.1007/BF01940884zbMath0848.68025OpenAlexW1965800860MaRDI QIDQ1918994

Marc J. van Kreveld, Pankaj K. Agarwal

Publication date: 23 July 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940884

zbMATH Keywords

intersection searchingefficient data structures

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items (5)

A technique for adding range restrictions to generalized searching problems ⋮ Further results on generalized intersection searching problems: Counting, reporting, and dynamization ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ EFFICIENT NON-INTERSECTION QUERIES ON AGGREGATED GEOMETRIC DATA ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range searching with efficient hierarchical cuttings
• The design of dynamic data structures
• Storing line segments in partition trees
• Partitioning arrangements of lines. II: Applications
• General methods for adding range restrictions to decomposable searching problems
• Applications of a new space-partitioning technique
• The number of edges of many faces in a line segment arrangement
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Intersection Queries in Curved Objects
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Amortized Computational Complexity
• Adding range restriction capability to dynamic data structures
• Algorithms for ray-shooting and intersection searching
• Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
• An optimal real-time algorithm for planar convex hulls
• A general approach to connected-component labeling for arbitrary image representations
• Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
• Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects
• GENERALIZED INTERSECTION SEARCHING PROBLEMS
• Space searching for intersecting objects

This page was built for publication: Connected component and simple polygon intersection searching