Line Drawing (Line Drawing)

Description

Given a line segment with endpoints $(x_0, y_0), (x_1, y_1)$ and a discrete graphical medium (like pixel-based displays and printers), draw/approximate the line segment on the medium, potentially with antialiasing.

Parameters

n: number of pixels the line goes through

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Naive algorithm	1940	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic
Digital Differential Analyzer	1940	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic
Bresenham's line algorithm	1965	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic	Time
Xiaolin Wu's line algorithm	1991	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic	Time
Gupta-Sproull algorithm	1981	$O(n)$	$O({1})$ auxiliary	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff