An optimal online algorithm for halfplane intersection

DOI10.1007/BF02948817MaRDI QIDQ5938679zbMATH OpenOpenAlexFDO

Authors Jigang Wu, Yongchang Ji, Guoliang Chen

Publication date 1 October 2001

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

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

zbMATH Keywords

complexitycomputational geometryintersection of halfplanesonline algorithm

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies and applications (68U99) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 3945383
• An optimal algorithm for intersecting line segments in the plane
• A new O(n \,n) algorithm for computing the intersection of convex polygons
• The power of geometric duality
• Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming

Cites work

• A new approach to the dynamic maintenance of maximal points in a plane
• Algebraic pruning: a fast technique for curve and surface intersection
• Does a point lie inside a polygon ?
• Finding the intersection of n half-spaces in time O(n log n)
• scientific article; zbMATH DE number 1003229 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems

Cited in

(2)

• On the complexity of halfspace area queries
• scientific article; zbMATH DE number 3945383 (Why is no real title available?)

This page was built for publication: An optimal online algorithm for halfplane intersection

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