A note on searching line arrangements and applications

DOI10.1016/J.IPL.2013.04.011MaRDI QIDQ2444761zbMATH OpenOpenAlexFDO

Authors Danny Z. Chen, Haitao Wang

Publication date 11 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.04.011

zbMATH Keywords

algorithm designcomputational geometryline arrangementpoints approximationvertex searching

Mathematics Subject Classification ID

Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Line arrangements and range search
• scientific article; zbMATH DE number 4060738
• An Optimal-Time Algorithm for Slope Selection
• Optimal slope selection via expanders
• Partitioning arrangements of lines. II: Applications

Cites work

• A deterministic algorithm for fitting a step function to a weighted point-set
• A randomized algorithm for weighted approximation of points by a step function
• An Optimal-Time Algorithm for Slope Selection
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximating points by a piecewise linear function: I
• Approximations and optimal geometric divide-and-conquer
• Computational geometry. Algorithms and applications.
• Diameter, width, closest line pair, and parametric searching
• EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION
• Fitting a Step Function to a Point Set
• Fitting a step function to a point set
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Optimal slope selection via cuttings
• Optimal slope selection via expanders
• Slowing down sorting networks to obtain faster sorting algorithms
• Sorting in \(c \log n\) parallel steps
• Weighted Rectilinear Approximation of Points in the Plane

Cited in

(19)

• A general framework for searching on a line
• Computing \(k\)-centers of uncertain points on a real line
• The two-center problem of uncertain points on a real line
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• scientific article; zbMATH DE number 4060738 (Why is no real title available?)
• An Optimal-Time Algorithm for Slope Selection
• scientific article; zbMATH DE number 1962801 (Why is no real title available?)
• One-dimensional \(k\)-center on uncertain data
• Efficient algorithms for the one-dimensional \(k\)-center problem
• An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
• Efficient and small representation of line arrangements with applications
• An O(n n)-time algorithm for the k-center problem in trees
• Searching for Point Locations Using Lines
• The two-center problem of uncertain points on trees
• A subquadratic time algorithm for the weighted k-center problem on cactus graphs
• Optimal slope selection via expanders
• The two-center problem of uncertain points on cactus graphs
• The connected k-vertex one-center problem on graphs
• The k-center problem of uncertain points on graphs

This page was built for publication: A note on searching line arrangements and applications

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