Rearranging a sequence of points onto a line

DOI10.1016/J.COMGEO.2022.101887MaRDI QIDQ2144451zbMATH OpenOpenAlexWikidataFDO

Authors Taehoon Ahn, Chaeyoon Chung, Hee-Kap Ahn, Sang Won Bae, Sang Duk Yoon, Jong Min Choi

Publication date 13 June 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2022.101887

zbMATH Keywords

point sequencerearrangementtrajectory

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Rearranging the points of a given sequence of points has many practical applications in computer graphics and image processing. So, in this paper, the problem of rearranging a sequence of weighted points in a plane is considered. These points have to be rearranged in such a way that any two consecutive points are at distance no more than their weight difference and the maximum distance between any two points is minimized. In this paper, algorithms are presented that compute optimal rearrangements for three variants of the problem either under the \(L_1\) metric or under the Euclidean metric.

Recommendations

• Weighted Rectilinear Approximation of Points in the Plane
• On the arrangement of point sets in the unit interval
• scientific article; zbMATH DE number 3910132
• An optimal way of moving a sequence of points onto a curve in two dimensions
• Ordinal algorithms for packing with target center of gravity

Cites work

• An efficient algorithm for determining the convex hull of a finite planar set
• Applications of Parametric Searching in Geometric Optimization
• Computational geometry. Algorithms and applications.
• Computing the width of a set
• Curve fitting by segmented straight lines
• Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming
• Efficient randomized algorithms for some geometric optimization problems
• Farthest line segment Voronoi diagrams
• Geometric applications of a randomized optimization technique
• scientific article; zbMATH DE number 1424289 (Why is no real title available?)
• scientific article; zbMATH DE number 6472585 (Why is no real title available?)
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• Linear-time algorithms for the farthest-segment Voronoi diagram and related tree structures
• Slowing down sorting networks to obtain faster sorting algorithms
• Sorting in \(c \log n\) parallel steps
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Cited in

(1)

• scientific article; zbMATH DE number 1163414 (Why is no real title available?)

This page was built for publication: Rearranging a sequence of points onto a line

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