A fast planar partition algorithm. I

DOI10.1016/S0747-7171(08)80064-8zbMATH Open0717.68104MaRDI QIDQ2638830FDOQ2638830

Authors: Ketan D. Mulmuley 

Publication date: 1990

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

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

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)

Cites Work

• Algorithms for Reporting and Counting Geometric Intersections
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Title not available (Why is that?)
• Reporting and counting segment intersections

Cited In (25)

• GUARDING ART GALLERIES BY GUARDING WITNESSES
• Farthest-polygon Voronoi diagrams
• A fast planar partition algorithm, II
• Partial order multiway search
• A binomial sum of harmonic numbers
• Optimal window queries on line segments using the trapezoidal search DAG
• Partitioning with two lines in the plane
• Constructing Planar Cuttings in Theory and Practice
• Average case analysis of dynamic geometric optimization
• 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
• Separating and shattering long line segments
• Untangling planar curves
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Markov incremental constructions
• Advanced programming techniques applied to CGAL's arrangement package

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)