---
_id: '13134'
abstract:
- lang: eng
  text: We propose a characterization of discrete analytical spheres, planes and lines
    in the body-centered cubic (BCC) grid, both in the Cartesian and in the recently
    proposed alternative compact coordinate system, in which each integer triplet
    addresses some voxel in the grid. We define spheres and planes through double
    Diophantine inequalities and investigate their relevant topological features,
    such as functionality or the interrelation between the thickness of the objects
    and their connectivity and separation properties. We define lines as the intersection
    of planes. The number of the planes (up to six) is equal to the number of the
    pairs of faces of a BCC voxel that are parallel to the line.
acknowledgement: The first author has been partially supported by the Ministry of
  Science, Technological Development and Innovation of the Republic of Serbia through
  the project no. 451-03-47/2023-01/200156. The fourth author is funded by the DFG
  Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’,
  Austrian Science Fund (FWF), grant no. I 02979-N35.
article_number: '109693'
article_processing_charge: No
article_type: original
author:
- first_name: Lidija
  full_name: Čomić, Lidija
  last_name: Čomić
- first_name: Gaëlle
  full_name: Largeteau-Skapin, Gaëlle
  last_name: Largeteau-Skapin
- first_name: Rita
  full_name: Zrour, Rita
  last_name: Zrour
- first_name: Ranita
  full_name: Biswas, Ranita
  id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
  last_name: Biswas
  orcid: 0000-0002-5372-7890
- first_name: Eric
  full_name: Andres, Eric
  last_name: Andres
citation:
  ama: Čomić L, Largeteau-Skapin G, Zrour R, Biswas R, Andres E. Discrete analytical
    objects in the body-centered cubic grid. <i>Pattern Recognition</i>. 2023;142(10).
    doi:<a href="https://doi.org/10.1016/j.patcog.2023.109693">10.1016/j.patcog.2023.109693</a>
  apa: Čomić, L., Largeteau-Skapin, G., Zrour, R., Biswas, R., &#38; Andres, E. (2023).
    Discrete analytical objects in the body-centered cubic grid. <i>Pattern Recognition</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.patcog.2023.109693">https://doi.org/10.1016/j.patcog.2023.109693</a>
  chicago: Čomić, Lidija, Gaëlle Largeteau-Skapin, Rita Zrour, Ranita Biswas, and
    Eric Andres. “Discrete Analytical Objects in the Body-Centered Cubic Grid.” <i>Pattern
    Recognition</i>. Elsevier, 2023. <a href="https://doi.org/10.1016/j.patcog.2023.109693">https://doi.org/10.1016/j.patcog.2023.109693</a>.
  ieee: L. Čomić, G. Largeteau-Skapin, R. Zrour, R. Biswas, and E. Andres, “Discrete
    analytical objects in the body-centered cubic grid,” <i>Pattern Recognition</i>,
    vol. 142, no. 10. Elsevier, 2023.
  ista: Čomić L, Largeteau-Skapin G, Zrour R, Biswas R, Andres E. 2023. Discrete analytical
    objects in the body-centered cubic grid. Pattern Recognition. 142(10), 109693.
  mla: Čomić, Lidija, et al. “Discrete Analytical Objects in the Body-Centered Cubic
    Grid.” <i>Pattern Recognition</i>, vol. 142, no. 10, 109693, Elsevier, 2023, doi:<a
    href="https://doi.org/10.1016/j.patcog.2023.109693">10.1016/j.patcog.2023.109693</a>.
  short: L. Čomić, G. Largeteau-Skapin, R. Zrour, R. Biswas, E. Andres, Pattern Recognition
    142 (2023).
date_created: 2023-06-18T22:00:45Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2023-10-10T07:37:16Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.patcog.2023.109693
external_id:
  isi:
  - '001013526000001'
intvolume: '       142'
isi: 1
issue: '10'
language:
- iso: eng
month: '10'
oa_version: None
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I02979-N35
  name: Persistence and stability of geometric complexes
- _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316
  grant_number: I4887
  name: Discretization in Geometry and Dynamics
publication: Pattern Recognition
publication_identifier:
  issn:
  - 0031-3203
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Discrete analytical objects in the body-centered cubic grid
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 142
year: '2023'
...
---
_id: '4125'
abstract:
- lang: eng
  text: "Let S denote a set of n points in the plane such that each point p has assigned
    a positive weight w(p) which expresses its capability to influence its neighbourhood.
    In this sense, the weighted distance of an arbitrary point x from p is given by
    de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi
    diagram for S is a subdivision of the plane such that each point p in S is associated
    with a region consisting of all points x in the plane for which p is a weighted
    nearest point of S.\r\n\r\nAn algorithm which constructs the weighted Voronoi
    diagram for S in O(n2) time is outlined in this paper. The method is optimal as
    the diagram can consist of Θ(n2) faces, edges and vertices.\r\n"
acknowledgement: The second author gratefully acknowledges discussions on the presented
  topic with David Kirkpatrick and Raimund Seidel.
article_processing_charge: No
article_type: original
author:
- first_name: Franz
  full_name: Aurenhammer, Franz
  last_name: Aurenhammer
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: Aurenhammer F, Edelsbrunner H. An optimal algorithm for constructing the weighted
    Voronoi diagram in the plane. <i>Pattern Recognition</i>. 1983;17(2):251-257.
    doi:<a href="https://doi.org/10.1016/0031-3203(84)90064-5">10.1016/0031-3203(84)90064-5</a>
  apa: Aurenhammer, F., &#38; Edelsbrunner, H. (1983). An optimal algorithm for constructing
    the weighted Voronoi diagram in the plane. <i>Pattern Recognition</i>. Elsevier.
    <a href="https://doi.org/10.1016/0031-3203(84)90064-5">https://doi.org/10.1016/0031-3203(84)90064-5</a>
  chicago: Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for
    Constructing the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>.
    Elsevier, 1983. <a href="https://doi.org/10.1016/0031-3203(84)90064-5">https://doi.org/10.1016/0031-3203(84)90064-5</a>.
  ieee: F. Aurenhammer and H. Edelsbrunner, “An optimal algorithm for constructing
    the weighted Voronoi diagram in the plane,” <i>Pattern Recognition</i>, vol. 17,
    no. 2. Elsevier, pp. 251–257, 1983.
  ista: Aurenhammer F, Edelsbrunner H. 1983. An optimal algorithm for constructing
    the weighted Voronoi diagram in the plane. Pattern Recognition. 17(2), 251–257.
  mla: Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing
    the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>, vol. 17,
    no. 2, Elsevier, 1983, pp. 251–57, doi:<a href="https://doi.org/10.1016/0031-3203(84)90064-5">10.1016/0031-3203(84)90064-5</a>.
  short: F. Aurenhammer, H. Edelsbrunner, Pattern Recognition 17 (1983) 251–257.
date_created: 2018-12-11T12:07:05Z
date_published: 1983-07-01T00:00:00Z
date_updated: 2022-01-27T14:06:27Z
day: '01'
doi: 10.1016/0031-3203(84)90064-5
extern: '1'
intvolume: '        17'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0031320384900645?via%3Dihub
month: '07'
oa_version: None
page: 251 - 257
publication: Pattern Recognition
publication_identifier:
  eissn:
  - 1873-5142
  issn:
  - 0031-3203
publication_status: published
publisher: Elsevier
publist_id: '1997'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An optimal algorithm for constructing the weighted Voronoi diagram in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 17
year: '1983'
...