A fast planar partition algorithm. I

DOI10.1016/S0747-7171(08)80064-8MaRDI QIDQ2638830zbMATH OpenFDO

Authors Ketan D. Mulmuley

Publication date 1990

Published in Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

randomized algorithmcomputer graphicsplanar partition problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Recommendations

• A fast planar partition algorithm, II
• Partitioning arrangements of lines. II: Applications
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Computing a Face in an Arrangement of Line Segments and Related Problems
• An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem

Cites work

• scientific article; zbMATH DE number 3451445 (Why is no real title available?)
• Algorithms for Reporting and Counting Geometric Intersections
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Reporting and counting segment intersections

Cited in

(25)

• GUARDING ART GALLERIES BY GUARDING WITNESSES
• Farthest-polygon Voronoi diagrams
• A fast planar partition algorithm, II
• A binomial sum of harmonic numbers
• Partitioning with two lines in the plane
• Optimal window queries on line segments using the trapezoidal search DAG
• Partial order multiway search
• Average case analysis of dynamic geometric optimization
• Constructing Planar Cuttings in Theory and Practice
• Division of a set of segments into nonintersecting parts on a discrete plane
• Reporting intersecting pairs of convex polytopes in two and three dimensions
• On the union of fat wedges and separating a collection of segments by a line
• Towards an optimal method for dynamic planar point location
• Finding the largest empty disk containing a query point
• Optimal randomized incremental construction for guaranteed logarithmic planar point location
• Adaptive Point Location in Planar Convex Subdivisions
• Divide-and-conquer in planar geometry
• Computing a Face in an Arrangement of Line Segments and Related Problems
• On-line construction of the upper envelope of triangles and surface patches in three dimensions
• Rounding Arrangements Dynamically
• Untangling planar curves
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Separating and shattering long line segments
• Advanced programming techniques applied to CGAL's arrangement package
• Markov incremental constructions

This page was built for publication: A fast planar partition algorithm. I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2638830)