de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Report

#### Proximity in arrangements of algebraic sets

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45295

Rieger,  Joachim
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)

1996-1-003
(Any fulltext), 10KB

##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Rieger, J.(1996). Proximity in arrangements of algebraic sets (MPI-I-1996-1-003). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A1A7-9
##### Abstract
Let \$X\$ be an arrangement of \$n\$ algebraic sets \$X_i\$ in \$d\$-space, where the \$X_i\$ are either parameterized or zero-sets of dimension \$0\le m_i\le d-1\$. We study a number of decompositions of \$d\$-space into connected regions in which the distance-squared function to \$X\$ has certain invariances. These decompositions can be used in the following of proximity problems: given some point, find the \$k\$ nearest sets \$X_i\$ in the arrangement, find the nearest point in \$X\$ or (assuming that \$X\$ is compact) find the farthest point in \$X\$ and hence the smallest enclosing \$(d-1)\$-sphere. We give bounds on the complexity of the decompositions in terms of \$n\$, \$d\$, and the degrees and dimensions of the algebraic sets \$X_i\$.