A replacement for Voronoi diagrams of near linear size

S. Har-Peled

doi:10.1109/sfcs.2001.959884

A replacement for Voronoi diagrams of near linear size

S. Har-Peled

Siebel School of Computing and Data Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

The decomposition of space providing an approximation to the distance function associated with the Voronoi diagram of near linear size was presented. Voronoi diagrams are a fundamental structure in geometric computing. The Voronoi diagram was induced by the distance function of a point-set. The nearest neighbor distance function returned the distance between q and its nearest point in the set.

Original language	English (US)
Pages (from-to)	94-103
Number of pages	10
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
DOIs	https://doi.org/10.1109/sfcs.2001.959884
State	Published - 2001
Event	42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States Duration: Oct 14 2001 → Oct 17 2001

ASJC Scopus subject areas

Hardware and Architecture

Online availability

10.1109/sfcs.2001.959884

Library availability

Discover UIUC Full Text

Cite this

@article{380b00dc965a42a4adce811738bfaf8f,

title = "A replacement for Voronoi diagrams of near linear size",

abstract = "The decomposition of space providing an approximation to the distance function associated with the Voronoi diagram of near linear size was presented. Voronoi diagrams are a fundamental structure in geometric computing. The Voronoi diagram was induced by the distance function of a point-set. The nearest neighbor distance function returned the distance between q and its nearest point in the set.",

author = "S. Har-Peled",

year = "2001",

doi = "10.1109/sfcs.2001.959884",

language = "English (US)",

pages = "94--103",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "42nd Annual Symposium on Foundations of Computer Science ; Conference date: 14-10-2001 Through 17-10-2001",

}

TY - JOUR

T1 - A replacement for Voronoi diagrams of near linear size

AU - Har-Peled, S.

PY - 2001

Y1 - 2001

N2 - The decomposition of space providing an approximation to the distance function associated with the Voronoi diagram of near linear size was presented. Voronoi diagrams are a fundamental structure in geometric computing. The Voronoi diagram was induced by the distance function of a point-set. The nearest neighbor distance function returned the distance between q and its nearest point in the set.

AB - The decomposition of space providing an approximation to the distance function associated with the Voronoi diagram of near linear size was presented. Voronoi diagrams are a fundamental structure in geometric computing. The Voronoi diagram was induced by the distance function of a point-set. The nearest neighbor distance function returned the distance between q and its nearest point in the set.

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

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

U2 - 10.1109/sfcs.2001.959884

DO - 10.1109/sfcs.2001.959884

M3 - Conference article

AN - SCOPUS:0035172304

SN - 0272-5428

SP - 94

EP - 103

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - 42nd Annual Symposium on Foundations of Computer Science

Y2 - 14 October 2001 through 17 October 2001

ER -

A replacement for Voronoi diagrams of near linear size

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this