Towards in-place geometric algorithms and data structures

Hervé Brönnimann; Timothy M. Chan; Eric Y. Chen

doi:10.1145/997817.997854

Towards in-place geometric algorithms and data structures

Hervé Brönnimann, Timothy M. Chan, Eric Y. Chen

Research output: Contribution to conference › Paper › peer-review

Abstract

For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

Original language	English (US)
Pages	239-246
Number of pages	8
DOIs	https://doi.org/10.1145/997817.997854
State	Published - Jan 1 2004
Externally published	Yes
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004

Other

Other	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country	United States
City	Brooklyn, NY
Period	6/9/04 → 6/11/04

Keywords

Convex hulls
In-place algorithms
Range searching
Voronoi diagrams

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/997817.997854

Fingerprint Dive into the research topics of 'Towards in-place geometric algorithms and data structures'. Together they form a unique fingerprint.

Cite this

@conference{3d39d36c95b2450bbf289086085daad9,

title = "Towards in-place geometric algorithms and data structures",

abstract = "For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.",

keywords = "Convex hulls, In-place algorithms, Range searching, Voronoi diagrams",

author = "Herv{\'e} Br{\"o}nnimann and Chan, {Timothy M.} and Chen, {Eric Y.}",

year = "2004",

month = jan,

day = "1",

doi = "10.1145/997817.997854",

language = "English (US)",

pages = "239--246",

note = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) ; Conference date: 09-06-2004 Through 11-06-2004",

}

TY - CONF

T1 - Towards in-place geometric algorithms and data structures

AU - Brönnimann, Hervé

AU - Chan, Timothy M.

AU - Chen, Eric Y.

PY - 2004/1/1

Y1 - 2004/1/1

N2 - For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

AB - For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

KW - Convex hulls

KW - In-place algorithms

KW - Range searching

KW - Voronoi diagrams

UR - http://www.scopus.com/inward/record.url?scp=4544357053&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4544357053&partnerID=8YFLogxK

U2 - 10.1145/997817.997854

DO - 10.1145/997817.997854

M3 - Paper

AN - SCOPUS:4544357053

SP - 239

EP - 246

T2 - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

Y2 - 9 June 2004 through 11 June 2004

ER -

Towards in-place geometric algorithms and data structures

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this